무지의 먹방 라이브

문제

2019 KAKAO BLIND RECRUITMENT
https://school.programmers.co.kr/learn/courses/30/lessons/42891

문제 요약

각 음식은 크기를 가지고 있고,

음식은 원형 테이블에 놓아져서 시간이 다 될때 까지 번호가 증가하는 순서대로 회전한다.

만약 다먹은 음식이면 건너뛴다.

시간이 다 지나고 다음 먹을 음식의 index값을 찾는 문제

풀이과정

크기가 가장 작은 음식을 힙큐에서 하나씩 꺼내서 시간안에 하나를 없앨 수 있으면 없앰

만약 음식을 시간안에 없앨 수 없으면 while 문 밖으로 나가서 남아있는 음식을 번호순으로 순서 매겨서 계산

코드

import heapq

def solution(food_times, k):
    answer = 0
    
    if sum(food_times) <= k:
        return -1

    food_len = len(food_times)

    hq = []
    for i in range(0, len(food_times)):  # 우선 순위 큐에 [음식 길이, 음식 번호]로 삽입
        heapq.heappush(hq, [food_times[i], i + 1])

    sum_foods = 0 # 현재까지 먹은 1개의 음식 크기
    while True:
        if hq[0][0] == sum_foods:
            heapq.heappop(hq)
            food_len -= 1
            continue
        if (hq[0][0] - sum_foods) * food_len > k : # 만약 음식 하나 다 못먹는 경우
            break

        min_len = heapq.heappop(hq)[0] - sum_foods
        k -= (min_len * food_len)
        sum_foods += min_len
        food_len -= 1
    result = sorted(hq, key=lambda x: x[1])
    answer = result[k % food_len][1]
    return answer

틀렸던 부분

📌 while문 안의 첫번째 조건을 빠트렸다.

왜 있어야 하냐면 만약 입력값이 [1,1,3,4]이고 k는 4이상이라고 치자

그럼 음식을 한바퀴 돌리면 [3, 4]가 남아야 한다.

근데 내 코드상으로는 [1, 3, 4]가 된다.

그렇기 때문에 만약 중복된 크기의 가장 작은 음식이 있을 때 같이 제거해줘야 하기 때문에 첫번째 조건식을 추가해줬다.

📌 while문안의 두번째 조건문에서 가장작은 음식을 볼때 현재까지 먹은 1개의 음식크기를 빼줘야 현재 상태의 음식의 크기이기 때문에 hq[0][0] - sum_foods을 해줘야 하는데 hq[0][0] - 이전 음식 크기를 해서 틀렸다.