LeetCode 1518. Water Bottles 자바 문제 풀이

문제 설명

• 문제: LeetCode 1518. Water Bottles
• 설명: 우리는 numBottles개의 물병을 가지고 있습니다. 빈 병 numExchange개를 새 물병 하나로 교환할 수 있습니다. 최대 몇 병의 물을 마실 수 있는지 계산하는 문제입니다.

접근 방식

아이디어:

• 초기에는 numBottles개의 물병을 모두 마십니다.
• 마신 후에는 빈 병이 numBottles개 생깁니다.
• 이 빈 병으로 새 물병을 교환합니다. 교환할 수 있는 만큼 새 물병을 마시고 다시 빈 병이 생기면 또 교환합니다.
• 빈 병의 개수가 numExchange보다 작아질 때까지 이 과정을 반복합니다.
• 마지막으로 총 마실 수 있는 물병의 수를 반환합니다.

알고리즘:

1. canDrink 변수를 초기 물병 개수로 설정합니다.
2. numBottles가 numExchange보다 크거나 같은 동안 반복합니다.
   1. 새로 얻은 물병의 수는 numBottles를 numExchange로 나눈 몫입니다. (numBottles / numExchange)
   2. newBottles 가 int 타입이므로, 소수는 버립니다.
   3. 개로 얻은 물병을 제외하고 남아 있는 물병 수는 numBottles를 numExchange로 나눈 나머지입니다. (numBottles % numExchange)
   4. 새로 얻은 물병의 수를 canDrink에 더합니다.
   5. 새로 얻은 물병 수와 교환 후 남은 빈 병의 수를 합하여 새로운 numBottles 값을 업데이트합니다.
3. 반복이 끝나면 canDrink 값을 반환합니다.

코드

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int canDrink = numBottles;

        while(numBottles >= numExchange){
            int newBottles = numBottles / numExchange;
            canDrink += newBottles;
            numBottles = newBottles + (numBottles % numExchange);
        }

        return canDrink;
    }
}

결론

시간 복잡도:

• 교환 과정에서 병의 수가 감소하므로 반복문은 최대 log(numBottles)번 실행됩니다.
• 따라서 시간 복잡도는 O(log n)입니다.

공간 복잡도:

• 추가적인 공간을 사용하지 않으므로 O(1)입니다.