반응형
문제 설명
- 문제: LeetCode 1518. Water Bottles
- 설명: 우리는
numBottles
개의 물병을 가지고 있습니다. 빈 병numExchange
개를 새 물병 하나로 교환할 수 있습니다. 최대 몇 병의 물을 마실 수 있는지 계산하는 문제입니다.
접근 방식
아이디어:
- 초기에는
numBottles
개의 물병을 모두 마십니다. - 마신 후에는 빈 병이
numBottles
개 생깁니다. - 이 빈 병으로 새 물병을 교환합니다. 교환할 수 있는 만큼 새 물병을 마시고 다시 빈 병이 생기면 또 교환합니다.
- 빈 병의 개수가
numExchange
보다 작아질 때까지 이 과정을 반복합니다. - 마지막으로 총 마실 수 있는 물병의 수를 반환합니다.
알고리즘:
canDrink
변수를 초기 물병 개수로 설정합니다.numBottles
가numExchange
보다 크거나 같은 동안 반복합니다.- 새로 얻은 물병의 수는
numBottles
를numExchange
로 나눈 몫입니다. (numBottles / numExchange) newBottles
가 int 타입이므로, 소수는 버립니다.- 개로 얻은 물병을 제외하고 남아 있는 물병 수는
numBottles
를numExchange
로 나눈 나머지입니다. (numBottles % numExchange) - 새로 얻은 물병의 수를
canDrink
에 더합니다. - 새로 얻은 물병 수와 교환 후 남은 빈 병의 수를 합하여 새로운
numBottles
값을 업데이트합니다.
- 새로 얻은 물병의 수는
- 반복이 끝나면
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)입니다.
반응형
'leetcode 문제 풀이' 카테고리의 다른 글
LeetCode 2582. Pass the Pillow 자바 문제 풀이 (0) | 2024.07.18 |
---|---|
LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points 자바 문제 풀이 (0) | 2024.07.18 |
LeetCode 1701. Average Waiting Time 자바 문제 풀이 (0) | 2024.07.16 |
LeetCode 1598. Crawler Log Folder 자바 문제 풀이 (0) | 2024.07.12 |
LeetCode 1823. Find the Winner of the Circular Game 자바 문제 풀이 (0) | 2024.07.09 |