[프로그래머스] 무지의 먹방 라이브

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42891

• 1번 음식부터 오름차순으로 1초씩 음식을 먹음
• K초 후 몇 번 음식을 먹고 있는가?
  • 더 섭취할 음식이 없다면 -1 반환하기

---

 

주요 아이디어

• {음식번호 : 소요시간} 딕셔너리 형태로 저장
• 오름차순으로 돌려가며 하나씩 빼주고, K초 후를 계산해준다

---

 

코드 구현 (Python 3)

def solution(food_times, k):
    answer = 0
    
    # dict 추가
    food_dict = {}

    for idx, time in enumerate(food_times):
        food_dict[idx] = time
    
    idx = 0
    
    # k번 반복
    while k:
        if food_dict[idx % len(food_times)] == 0:
            idx += 1
            continue
        else:
            food_dict[idx % len(food_times)] -= 1
            k -= 1; idx += 1
    
    return idx % len(food_times) + 1

시간초과....

 

---

 

실패 원인

• 하나씩 빼주는 방식으로는 계속 시간초과가 발생
• 다른 방법이 필요
• 풀이 방법이 떠오르지 않아서 유튜브 풀이 영상을 참조했다

https://www.youtube.com/watch?v=zpz8SMzwiHM

 

유튜브 영상 캡처본

하나씩 돌려가면서 빼주지 말고, 소요시간에 따른 오름차순 정렬을 진행한 후 한꺼번에 빼주자

유튜브 영상 캡처본

이런 식으로 묶음으로 빼주면 시간 효율성을 대폭 향상시킬 수 있다

 

---

 

코드 재구현 (Python 3)

import heapq

def solution(food_times, k):
    # 애초에 먹을 음식 안남으면 -1 반환
    if k >= sum(food_times):
        return -1
    
    food_list = []
    length = len(food_times) # 남은 음식 개수

    for i in range(length):
		    # (남은 시간, 음식 번호)
		    # 최소 힙을 통한 음식 시간 정렬
        heapq.heappush(food_list, [food_times[i], i+1])
    
    time = 0
    
    # 블럭 단위로 뺄만큼 K가 남았다면 -> 묶음 단위로 빼주기
    while (food_list[0][0] - time) * length < k:
        k -= (food_list[0][0] - time) * length
        time += food_list[0][0] - time
        length -= 1
        heapq.heappop(food_list)
		
		# 최종적으로 K초에 몇 번째 음식이 오는지 구하기
    result = sorted(food_list, key = lambda x: x[1])
    answer = result[k % length][1]

    return answer

 

---

 

제출 결과