난이도: 1 / 풀이 시간: 30분
link: https://school.programmers.co.kr/learn/courses/30/lessons/42891
평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어졌고 고민 끝에 카카오 TV 라이브 방송을 하 기로 마음먹었습니다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.
회전판에 먹어야 할 N 개의 음식이 있다.
각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.
무지는 다음과 같은 방법으로 음식을 섭취한다.
- 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
- 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
- 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.- 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.
무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.
무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.
각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.
풀이 특징
- 시뮬레이션 형식으로 완전탐색할 경우 시간초과가 된다.
- 시간초과의 경우 log(N) 형식을 고민해야 한다.
- PriorityQueue (heapq) 를 사용하여 음식시간이 적은 순으로 음식을 확인해야 한다.
- 남은 시간과 한 음식이 제거될 때 까지의 시간(남은 음식수 * 음식시간이 가장 적은 음식)을 비교한다.
- 한 음식이 제거될 수 있을 경우 해당 음식을 heapq 에서 제거, 다음 음식에서 해당음식을 먹은 시간을 빼야하므로 마지막에 제거된 음식의 시간을 저장한다.
- 한 음식이 제거될 때 까지 전체 음식을 못 먹는 경우 해당 음식을 포함하여 음식번호 순서로 정렬한다.
- 정렬 후 남은 시간을 남은 음식개수로 나눈 나머지 값이 k초 후 먹을 음식의 인덱스가 된다.
- 따라서 해당 인덱스의 음식 번호를 반환한다.
import heapq
def solution(food_times, k):
# k초가 되기전까지 음식을 다 먹을 수 있는 경우
if sum(food_times) <= k:
return -1
# 모든 음식을 시간순으로 정렬해야 한다.
# 마지막에 음식번호를 출력해야 하기 때문에 heapq(시간, 음식번호) 삽입
q = []
for i in range(len(food_times)):
heapq.heappush(q, (food_times[i], i+1))
sumTime = 0 # 섭취 누적시간
removedTime = 0 # 직전에 제거된 음식의 시간
# 남은 음식의 개수
foodCount = len(food_times)
while True :
now = heapq.heappop(q)
nowFoodTime = now[0]
roundTime = foodCount * (nowFoodTime - removedTime)
# 남은 시간이 해당 음식기준 전체음식을 먹는데 걸리는 시간보다 작은 경우 -> 먹지못하고 종료
if (k - sumTime) < roundTime:
heapq.heappush(q, now)
break;
# 누적시간 += 현재 음식기준 전체 음식을 먹는데 걸리는 시간
sumTime += roundTime
# 남은 음식의 개수 -1
foodCount -= 1
# 직전 제거된 음식 반영
removedTime = nowFoodTime
# 남은 음식들을 음식번호 순으로 정렬한다
remainFoods = sorted(q, key=lambda x: x[1])
# 마지막 음식 + 1 위치는 (남은 시간 % 남은 음식개수)
return remainFoods[(k - sumTime)%foodCount][1]
iOS Developer