[1스4코2파] # 190. LeetCode 875. Koko Eating Bananas

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (190차)
[4코1파] 2023.01.13~ (182일차)
[1스4코1파] 2023.04.12~ (93일차)
[1스4코2파] 2023.05.03 ~ (71일차)

Today :

2023.07.12 [190일차]
binary_search
875. Koko Eating Bananas

875. Koko Eating Bananas

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

문제 설명

바나나를 좋아하는 koko가 있는데 바나나 다발이랑, 각 다발에 붙어있는 바나나는 다르다
주어진 h 내에 바나나 전체를 먹는 최소의 시간을 반환한다!
시간당 먹을 수 있는 바나나의 개수가 한정되어 있음

만약에 모든 바나나를 주어진 h가 8개이고 각 다발이 [1,2,6,13] 이라면
바나나를 먹는 시간 hour가 1 이면, 1번째 바나나 다발을 먹는데 1시간,
2번째 바나나 다발을 먹는데 2시간 , 3번째 바나나 다발을 먹는데 6시간, 4 번째 바나나 다발을 먹는데 13시간으로 1+2+6+13 = 22가 소요된다.
h가 8이므로, 8에 해당하는 최소의 시간을 구해야한단 말씀

문제 풀이 방법

brute force로 풀면 time complextity 발생하므로
binary search로 풀면 됨

left, right를 주고, 보통의 인덱스를 찾는 방법에서 left, right를 각 0, 주어진 배열의 길이-1 로 줬지만 여기서는 바나나의 수를 세는 것이므로 left, right를 1과 배열의 길이로 줌
주어진 hours에 해당하는 만큼 바나나 piles에 대한 몫의 값, 나머지 바나나가 있다면 몫+1 의 값을 주고 주어진 hours에 해당하는 지 binary search로 찾는다
바나나를 다 먹기에 소요되는 시간이 target hours 보다 크면 left를 mid +1 ,
hours보다 작다면 right를 mid-1로 주면서 좁혀나간다.

내 코드

import math
class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        left, right = 1, max(piles)
        ans = right

        while left<=right:
            mid = (left+right)//2
            hours = 0
            for p in piles:
                hours += math.ceil(p/mid)

            if hours <= h:
                ans = min(ans, mid)
                right = mid-1
            else:
                left = mid+1
        return ans

증빙

여담

코코야 바나나 그냥 먹어 따지지말고
근데 바나나? 바나나캣?