문제링크
문제 해설
무지는 1번부터 N번까지의 음식을 번호 증가순으로 섭취한다. 각 음식은 섭취하는 시간이 있고, N번 음식 섭취 후에는 1번으로 돌아온다.
- 1초동안 섭취하고 제일 가까운 다음 번호 음식을 섭취한다고 가정
- 다음 음식 갖고오는데에 걸리는 시간은 없다고 가정
- 시간안에 다 먹으면 -1 리턴
- K초 뒤 무지가 먹을 음식 번호는 ??
IN
Food_times : 각 음식을 모두 먹는데 걸리는 시간
K : 시간 k초
OUT
K초 뒤 무지가 먹을 음식의 번호
문제 풀이
시도 1
Greedy로 분류된 만큼 시간이 제일 적게 걸리는 음식부터 확인하기로 했다.
Enumerate함수를 이용해 각 음식별 시간에 인덱스를 매기고, 리스트에서 먹는데 제일 적게 걸리는 음식부터 처리했다.
제일 적게 걸리는 음식을 다 먹는데 걸리는 시간 (minval * len(food))를 k에서 빼고 k가 0보다 작아질때까지 while문을 돌렸다. 제일 짧게 걸리는 음식을 딕셔너리에서 지우고, 각 음식별 남은 시간을 직접 딕셔너리에서 뺐는데 시간초과가 났다. 지금 생각해보니까 소요시간이 제일 짧은 음식이 두개라면 ??? 처리가 안될 것 같다.
시도 2
모르겠어서 결국 답 봤다. 포인트는
- 시간 적게 걸리는 음식을 min등이 아닌 우선순위 큐로 구현
- K나 리스트를 직접 조작하지 않고 총 시간과 이전 음식 시간, 지금 음식시간으로 값을 구함
import heapq
def solution(food_times, k):
answer = 0
food = []
if sum(food_times) <= k:
return -1
#힙에 넣기
for i in range(len(food_times)):
heapq.heappush(food, (food_times[i], i+1))
time = 0 #먹기위해 총 사용한 시간
previous = 0 #직전에 다 먹은 음식 시간
length = len(food_times) #남은 음식의 갯수
while time + ((food[0][0] - previous) * length) <= k:
now = heapq.heappop(food)[0]
time += (now - previous) * length
length -= 1 #다 먹은 음식 뺴기
previous = now
result = sorted(food, key = lambda k : k[1])
return result[(k-time) % length][1]
문제 해설
삽질하면서 배운거
-
딕셔너리에서 최소 value
minval = min(food.values()) -
딕셔너리에서 최소 value 가지는 key
minidx = min(food.key(), key = lambda : food[k]) -
딕셔너리에서의 포문
for key, val in food.items(): print(key, val)
아직은 어떤 자료구조를 써야 효율적일지 잘 떠오르지 않는다 ,,,,, ㅠ ㅠ
Hongik CE