[Programmers/프로그래머스] 2019 KAKAO BLIND RECRUITMENT [코딩테스트]

1. [Lv. 2] 오픈채팅방
2. [Lv. 1] 실패율
3. [Lv. 2] 후보키
4. [Lv. 4] 무지의 먹방 라이브
5. [Lv. 3] 길 찾기 게임
6. [Lv. 3] 매칭 점수
7. [Lv. 4] 블록 게임

📌 문제

---

📝 제한사항

---

💻 입출력 예

---

📖 입출력 예에 대한 설명

---

📌 풀이

---

import heapq

def solution(food_times, k):
    if sum(food_times) <= k:    # 방송이 중단되기 전에 모든 음식을 섭취할 수 있다면
        return -1               # 방송 중단 후 더 섭취할 음식이 없으므로 return -1
    
    heap = []                   # 필요 섭취 시간이 작은 순서대로 우선순위 큐
    for idx, food_time in enumerate(food_times):    # 음식번호, 섭취시간
        heapq.heappush(heap, (food_time, idx + 1))  # (섭취시간, 음식번호)
    
    sum_used_time = 0               # 섭취 시간 합계
    pre_used_time = 0               # 이전 섭취 시간
    num_left_food = len(food_times) # 남은 음식의 수
    
    # 섭취 시간 합계 + (현재 섭취 시간 - 이전 섭취 시간) * 남은 음식 수 <= 장애 발생 시간
    while sum_used_time + (heap[0][0] - pre_used_time) * num_left_food <= k:
        food_time, food_idx = heapq.heappop(heap)
        sum_used_time += (food_time - pre_used_time) * num_left_food
        num_left_food -= 1
        pre_used_time = food_time
    
    # 음식 번호 순대로 정렬, 장애 발생까지 남은 시간 % 남은 음식 개수 = 장애 복구 후 먹을 음식
    answer = sorted(heap, key=lambda x: x[1])
    return answer[(k - sum_used_time) % num_left_food][1]

📖 해설

---

1. heapq로 구현된 우선순위 큐는, 필요 섭취 시간이 작은순으로 정렬되어있다.
2. sum_used_time + (heap[0][0] - pre_used_time) * num_left_food <= k
   현재 음식을 완전히 섭취할 때까지 필요한 시간이 장애 발생시간 보다 적은지 확인하는 조건식
3. (food_time - pre_used_time) * num_left_food
   (현재 음식 필요 섭취 시간 - 이전 음식 필요 섭취 시간) * 남은 음식 개수
   이전 음식을 완전히 섭취하기 위해 회전판을 돌며 현재 음식도 일부 섭취했을 것이므로
   현재 음식 필요 섭취 시간 - 이전 음식 필요 섭취 시간.
   이후 현재 음식을 마저 완전히 섭취하기 위해,
   남은 음식을 포함해 회전판을 도는 시간을 구해야 하므로 x 남은 음식 개수