(Python3) - LeetCode (Medium) : 1760. Minimum Limit of Balls in a Bag

https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/

이분 탐색 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

left, right를 선언해 각각 1, nums의 원소의 최댓값을 저장합니다.

📔 풀이과정

1. while left <= right로 하면 왜 안 되는가?

while left < right 조건은 일반적으로 이진 탐색에서 범위를 계속 좁혀가며 특정 값에 수렴할 때 사용하는 형태입니다. 반면, while left <= right는 정확히 값을 찾거나 특정 조건이 충족되는 순간 탐색을 종료하는 데 주로 사용됩니다.

이 문제에서는 최적의 값을 찾기 위해 left와 right가 수렴하는 최종 지점까지 좁혀가야 합니다.

• left <= right로 하면 무한 루프에 빠질 가능성이 있음:
  • 예를 들어, mid = (left + right) // 2로 계산하고 범위를 조정할 때 left와 right의 업데이트가 제대로 이뤄지지 않으면 루프가 끝나지 않을 수 있습니다.
  • left < right는 수렴을 전제로 작성되었으므로, 종료 조건을 더 간단히 보장할 수 있습니다.

---

2. 왜 left가 0이면 안 되는가?

left = 0으로 초기화하면 mid = (0 + right) // 2에서 0이 포함될 수 있습니다. 하지만 이 문제의 조건에서 mid는 1 이상이어야 의미가 있습니다.

• mid는 공을 나누는 기준이 됩니다. mid = 0이면 공의 크기를 무한히 줄이는 상황이 발생해 문제가 성립하지 않습니다.
• 따라서 left는 최소한 1 이상이어야 합니다. 초기값으로 left = 1로 설정하면 문제에서 요구하는 모든 케이스를 커버할 수 있습니다.

---

3. 왜 right = mid이고, right = mid - 1이 아닌가?

right = mid를 사용하는 이유는, 현재의 mid가 조건을 만족하는 경우에도, 더 작은 값으로 조건을 만족할 가능성이 있기 때문입니다.

• 이 문제는 최적의 mid를 찾는 문제이므로, 조건을 만족한다고 바로 종료하지 않고 더 작은 값이 있는지 확인해야 합니다.
• right = mid - 1을 사용하면, 조건을 만족하는 값을 지나쳐서 올바른 결과를 놓칠 가능성이 있습니다.

---

예시로 이해하기

입력 예시:

python

Copy code

nums = [9, 6, 3] maxOperations = 2

초기 상태:

• left = 1, right = max(nums) = 9

이진 탐색 과정:

1. 첫 번째 루프:
   • mid = (1 + 9) // 2 = 5
   • tot = sum((x-1)//mid for x in nums) = (9-1)//5 + (6-1)//5 + (3-1)//5 = 1 + 1 + 0 = 2
   • tot == maxOperations, 조건 만족.
     • right = mid = 5 (더 작은 값을 탐색하기 위해)
2. 두 번째 루프:
   • mid = (1 + 5) // 2 = 3
   • tot = sum((x-1)//mid for x in nums) = (9-1)//3 + (6-1)//3 + (3-1)//3 = 2 + 1 + 0 = 3
   • tot > maxOperations, 조건 불만족.
     • left = mid + 1 = 4
3. 세 번째 루프:
   • mid = (4 + 5) // 2 = 4
   • tot = sum((x-1)//mid for x in nums) = (9-1)//4 + (6-1)//4 + (3-1)//4 = 2 + 1 + 0 = 3
   • tot > maxOperations, 조건 불만족.
     • left = mid + 1 = 5

최종 상태:

• left == right == 5에서 종료.
• 결과: right = 5

📔 정답 출력 | 반환

right를 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        left, right = 1, max(nums)
        while left < right:
            mid = (left + right) // 2
            tot = sum((x-1)//mid for x in nums)
            if tot <= maxOperations:
                right = mid
            else:
                left = mid + 1
        return right

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.