[이취코] 알고리즘 유형별 기출문제: 그리디 - 6. 무지의 먹방 라이브 (Python)

6. 무지의 먹방 라이브

• 2019 카카오 신입 공채 기출

문제

• 회전판에 먹어야 할 N개의 음식이 있다. 각 음식에는 1부터 N까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음 방식으로 음식을 섭취한다.
  • 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
  • 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞에 온다.
  • 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다. 다음 음식이란 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
  • 회전판이 다음 음식을 무지 앞으로 가져오는 데 걸리는 시간은 없다고 가정한다.
• 무지가 먹방을 시작한 지 K초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다. 무지는 네트워크 정상화 후 방송을 다시 이어갈 때, 몇 번 음식부터 섭취해야 하는 지 알고자 한다.
• 각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return하도록 solution 함수를 완성하라.

제한 사항

• 문제 조건
  • food_times는 각 음식을 모두 먹는 데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
  • k는 방송이 중단된 시간이다.
  • 더 섭취할 음식이 없다면 -1을 반환하라.
• 정확성 테스트 제한 사항
  • 1≤ len(food_times) ≤ 2,000
  • food_times의 원소는 1≤n≤1,000 인 자연수
  • k는 1≤k≤2,000,000인 자연수
• 효율성 테스트 제한 사항
  • 1≤ len(food_times) ≤ 200,000
  • food_times의 원소는 1≤n≤1,00,000,000 인 자연수
  • k는 1≤k≤2*10^13인 자연수

예시

food_times = [3, 1, 2] / k = 5 / result = 1

0~1초 동안 1번 음식 섭취 / 남은 시간 [2, 1, 2]

1~2초 동안 2번 음식 섭취 / 남은 시간 [2, 0, 2]

2~3초 동안 3번 음식 섭취 / 남은 시간 [2, 0, 1]

3~4초 동안 1번 음식 섭취 / 남은 시간 [1, 0, 1]

4~5초 동안 (2번 음식은 다 먹었으므로) 3번 음식 섭취 / 남은 시간 [1, 0, 0]

5초에서 네트워크 장애가 발생 - 1번을 섭취할 차례에 중단되었으므로, 장애 복구 후 1번부터 다시 먹기 시작

풀이

대표적인 풀이는 최소 힙(우선순위 큐)을 이용해 푸는 것이다. 먹는데 걸리는 시간이 가장 짧은 음식부터 힙에서 소거해 가면서 남은 음식에 대해 몇 번째 음식인지 순서를 찾는 것이다.

 

이를 구현하는 기본적인 아이디어는 이렇다.

 

1. for문을 돌며 힙에 (food_times[i], i+1) 쌍 넣기 (먹는데 걸리는 시간, 해당 음식의 번호)

2. k번째로 먹기 전에 힙의 최상단에 있는 음식(가장 먹는데 걸리는 시간이 짧은 음식)을 다 먹을때까지 테이블을 돌릴 수 있는 지 확인

2-1. 만약 k번 전에 먹을 수 있다면 현재까지 먹은 순서에 (지금 먹는 음식의 소요 시간 - 직전까지 먹은 음식의 소요 시간) * 남은 음식의 수)를 더한다. 이전에 계산한 순서(이미 먹은 음식의 양)는 포함하지 않기 위해 이렇게 계산한다. 계산 후 다음 힙의 최상단 음식에 대해 이 연산을 반복한다. 

2-2. 만약 k번 전에 먹을 수 없다면 루프를 빠져나와 남은 음식에 대해 k번째 먹을 음식의 순서를 계산한다. 현재 힙이 음식 섭취 시간을 기준으로 정렬되어 있으므로 이걸 음식 번호 순으로 다시 정렬하고, 남은 섭취 순서 번째의 음식의 원래 번호를 출력한다.

 

개인적으로 2-2 연산 과정이 이해가 한 번에 안돼서 아래처럼 예시를 가정하고 로직을 따라가 보았다. 최소 힙에서는 food_times를 기준으로 정렬했다가 답을 구할때는 다시 음식 번호 순으로 정렬한다는 점을 인식하면 쉽게 이해할 수 있을 것이다. 

 

food_times = [4, 6, 10, 8]

k = 24

------------------------------------------------------------

cur_sum = 0

past_food = 0

all_cnt = 4

------------------------------------------------------------

q = [(4, 1), (6, 2), (8, 4), (10, 3)]

→ while 0 + (4-0) * 4 < k (좌변 16)

4 다 섭취

q = [(6, 2), (8, 4), (10, 3)]

cur_sum = 16

past_food = 4

all_cnt = 3

------------------------------------------------------------

→ while 16 + (6-4) * 3 < k (좌변 22)

6 다 섭취

q = [(8, 4), (10, 3)]

cur_sum = 16 + 6

past_food = 6

all_cnt = 2

------------------------------------------------------------

→ while 22 + (8-6) * 2 < k (좌변 26)

루프 탈출

------------------------------------------------------------

힙에 남아있는 음식을 다시 원래의 음식 순서대로 정렬하고

result = sorted(q, key=lambda x: x[1])

q: [(10, 3), (8, 4)]

힙에서 (남은 먹방 횟수를 남은 음식 길이로 나눈 나머지)번째에 있는 음식의 원래 순서를 반환

return result[(k - cur_sum) % all_cnt][1]

(24 - 22) % 2 = 0

result[0][1] 출력 -> 3 출력

# 그리디 - 6. 무지의 먹방 라이브
import heapq

def solution(food_times, k):
    if sum(food_times) <= k:
        return -1
    q = []
    for i in range(len(food_times)):
        heapq.heappush(q, (food_times[i], i + 1)) # 음식 섭취 시간, 음식 번호 
    cur_sum = 0 # 지금까지 먹은 시간
    past_food = 0 # 직전까지 먹은 음식의 food_times
    all_cnt = len(q) # 큐에 남아있는 음식의 총 수
    
    while cur_sum + (q[0][0] - past_food) * all_cnt <= k:
        now_food = heapq.heappop(q)
        cur_sum += (now_food[0] - past_food) * all_cnt
        all_cnt -= 1
        past_food = now_food[0]
    
    result = sorted(q, key=lambda x: x[1])
    return result[(k-cur_sum) % all_cnt][1]