LeetCode [1518]: Water Bottles

📌 LeetCode [1518]: Water Bottles

🔗 문제 링크

---

문제 설명 📄

초기에는 numBottles개의 물병을 가지고 있으며, 빈 병 numExchange개를 새 물병 1개로 교환할 수 있습니다.
최대로 마실 수 있는 물병의 개수를 반환하세요.

---

문제 접근 방식 📋

1. 시뮬레이션 기반 접근:
   • 현재 물병 개수를 소비하며 마십니다.
   • 마신 후 빈 병의 개수를 계산하여 새 물병으로 교환.
   • 빈 병의 수가 numExchange 미만이 되면 반복 종료.
2. 병 교환 로직:
   • numBottles: 현재 가지고 있는 물병 개수.
   • binBottles: 현재 가지고 있는 빈 병의 개수.
   • 매번 마신 병의 수를 누적하며, 교환 후 남은 빈 병을 갱신.

---

Solution 💻

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        answer = 0
        binBottles = 0

        while numBottles > 0:
            answer += numBottles
            binBottles += numBottles
            numBottles = binBottles // numExchange
            binBottles %= numExchange

        return answer

시간 복잡도 분석 ⏲️

• 시간 복잡도: ( O(log(numBottles)) )
  • 매번 병을 마신 후 교환 가능 병 수가 감소하기 때문에 로그 시간 복잡도.
• 공간 복잡도: ( O(1) )
  • 상수 크기의 변수만 사용.

---

리팩토링 🛠️

개선된 코드

class Solution:
    def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
        return numBottles + (numBottles - 1) // (numExchange - 1)

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도: ( O(1) )
  • 수학적 계산만 수행.
• 공간 복잡도: ( O(1) ).

---