무지의 먹방 라이브

programmers.co.kr/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브

def solution(food_times, k):
    if sum(food_times) <= k: # 모든 음식을 먹는 시간 <= 방송 중단 시간 : k초 이후 남은 음식이 없음 
        return -1
    
    def check(mid_k): # x초 걸리는 음식을 다 먹을때까지 식사하는데 걸리는 시간 반환
        return sum([mid_k if i >= mid_k else i for i in food_times])
    
    mn, mx = 0, max(food_times) # 식탁에 있는 음식의 최소 소요시간, 최대 소요시간 
    while mn < mx - 1: # 이분탐색
        mid = (mx + mn) // 2
        if k < check(mid): # mid초 걸리는 음식을 다 먹었을때 k를 초과하면 max 조정
            mx = mid 
        else: # mid초 걸리는 음식을 다 먹었는데 k가 남아 있으면 min 조정
            mn = mid
    
    k -= check(mn) # k에서 check(이분탐색 결과)를 빼줌.
    return [i + 1 for i, t in enumerate(food_times) if t > mn][k] # 남은 음식중 k번째 음식 번호

→ 이분탐색 min 초기값을 0으로 한 이유는 [1,1,1], k = 2 와 같은 경우를

이분탐색 이후 처리할 필요가 없도록 한 것. 

 

이분탐색에서 빠져 나온뒤 max는 고려할 필요 x

(if k < check(mid) 의 경우에만 max = mid이므로.)

 

징검다리 건너기 문제와 비슷한듯.