[Leetcode] 875. Koko Eating Bananas(x)

1. problem : 

https://leetcode.com/problems/koko-eating-bananas/

 

2. solution 1 :

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        def canFinish(piles,speed,h):
            time = 0 
            for pile in piles:
                time += (pile - 1) // speed + 1 
            return time <= h 

        left,right = 1 , max(piles) 
        while left < right:
            mid = (left + right) // 2 
            if canFinish(piles,mid,h):
                right = mid 
            else:
                left = mid + 1 
        return left

koko가 바나나를 먹을 수 있는 최대의 개수는 1개에서 max(piles) 개다. 나는 여기서 탐색할 거 빠르게 하면 좋다는 생각에 도달을 못했다. 따라서, 1~max(piles)는 정렬되어 있기 때문에, 이진트리를 사용 가능하다. 

 

canFinish라는 함수를 보면, return 값이 time <= h 인데, time == h 도 포함하기 때문에, right = mid - 1이 아닌, mid로 옮겨주어야 한다. 왜냐하면, time == h 일 때의 해가 오직 하나일 수 있는데, mid -1로 해버리면, 값을 찾지 못하는 error가 발생한다.  이때, canFinish함수의 return 값이 time <= h에서 time == h 인 경우, right = mid로 옮기게 된다. 만약 time >= h 가 return값이었다면, 이 조건이 참일 때, left = mid로 설정해야 하는데, 이 경우, 최댓값을 찾는 문제로 바뀌어버린다.