Q06. 무지의 먹방 라이브
🐣문제
회전판에 먹어야 할 N 개의 음식이 있다.
각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.
무지는 다음과 같은 방법으로 음식을 섭취한다.
- 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
- 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
+ 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.- 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.
무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.
무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.
각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.
프로그래머스 링크 | https://programmers.co.kr/learn/courses/30/lessons/42891
🐥풀이
우선 요약한 풀이는 다음과 같다.
1. heapq를 활용해서 음식을 먹는 시간을 기준으로 오름차순으로 큐에 시간과 음식 번호를 삽입한다.
2. 주어진 시간(k초) 내에 먹어치울 수 있는 음식은 큐에서 삭제한다.
3. 남은 음식들을 음식 번호를 기준으로 오름차순으로 재배열 한다.
4. (삭제한 음식들을 먹어치우고 남은 시간)%(남은 음식 수)가 남은 음식 배열의 index가 된다.
이 문제의 핵심은 먹을 수 있는 음식부터 먹어버리기이다.
그러기 위해서는 먹는 시간이 작은 음식부터 차례로 정렬해야하는데, 이는 heapq로 해결할 수 있다. 즉, 큐에는 [시간, 번호] 정보가 시간 기준 오름차순으로 정렬되어 저장된다.
정렬되었으면 큐에서 음식 정보를 하나씩 빼낸다. (음식 먹는 시간을 time, 음식 번호를 num이라고 하겠다. 또한, 전 음식을 먹는 시간을 previous라는 변수에 저장하겠다.)
k>=(time-previous)x(남은 음식의 개수)이면 해당 음식 하나를 시간 내에 모두 먹을 수 있다. (time-previous)x(남은 음식의 개수)는 음식 하나를 모두 먹는데 소요되는 시간이다.
+1초마다 회전판이 돌아가기 때문에 (남은 음식의 개수)을 곱해주어야 한다.
+전 음식을 먹으면서 이미 한바퀴를 돌았기 때문에 previous를 빼주어야 한다.
음식을 시간 내에 먹었으므로 k -= (time-previous)x(남은 음식의 개수) 와 previous = time 로 처리해주어야 한다.
k<(time-previous)x(남은 음식의 개수)이면 시간 내로 음식을 먹을 수 없다. 음식 시간을 작은 순으로 판단해왔기 때문에 앞으로 남은 음식도 더 이상 먹을 수 없다. 따라서 break로 과정을 종료한다.
종료 후에 남은 음식들은 음식 번호를 기준으로 오름차순 재정렬한다. 정렬 후에 (남은 시간 k)%(남은 음식 수) 인덱스에 있는 음식이 네트워크 복구 후 먹을 차례인 음식 번호가 된다.
단, 입력값인 food_times의 합이 k를 넘기지 않으면 방송 종료 전에 모든 음식을 먹을 수 있으므로 -1을 반환해야 한다.
🐓코드
import heapq
def solution2(food_times, k):
# 방송 종료 전에 다 먹는 경우
if sum(food_times)<=k: return -1
result, previous, q, num = -1, 0, [], len(food_times)
for i in range(len(food_times)):
heapq.heappush(q,[food_times[i], i+1])
while q:
# (먹는 시간) = (남은 음식)*(음식 개수)
time = (q[0][0]-previous)*num
if k>=time:
k -= time
# 시간 내에 다 먹음! 음식 빼! 시간은 previous에 저장!
previous, _ = heapq.heappop(q)
num -= 1 # 남은 음식 개수 업데이트
else:
# 시간 내에 못 먹음 ㅠㅠ
idx = k%num # k초 동안 (남은 음식 개수)만큼 돌고 도착한 지점
q.sort(key=lambda x:x[1]) # 음식 번호 순으로 재정렬
return q[idx][1] # 도착한 지점에 있는 음식의 번호
return result⭐2022.03.31
지이인짜 어려웠다 ㅠㅠ 처음에는 읭 왜 greedy지?라는 마음으로 무작정 반복문 돌리면서 하나하나 시간 빼가면서 판단했는데 당연히 시간초과~! 큐를 사용해서 음식 하나씩 빼고 다시 넣고도 해봤지만 정확성은 통과하였으나 효율성에서 실패 ㅠㅠ 더 이상 모르겠어서 풀이 찾아보고 진짜 이런 신박한 풀이방식이 다 있나 싶었다 ㅋㅅㅋ 아~ 이래서 그리디구나~ 풀이과정 신박한걸~~ 어려워!!
1트) 반복문 돌리면서 하나하나 판단하기 (실패)
i, count = 0, 0
while count<k: # k초 먹으면 끝남
if food_times[i%len(food_times)]!=0: # 0이 아닐 때 음식 먹었음(1초)
food_times[i%len(food_times)] -= 1
count += 1
#print(food_times, count)
i += 1 # 1이상인 음식만 먹기위해 인덱스++
if food_times.count(0)==len(food_times): # 음식 다 먹음
print(-1)
else: # 남은 음식 중 먹어야 할 음식
print(i%len(food_times)+1)2트) 큐에 넣고 빼면서 판단하기 (정확성 통과, 효율성 실패)
def solution(food_times, k):
food = [[i+1, food_times[i]] for i in range(len(food_times))]
for _ in range(k):
# 더 먹을 음식 없으므로 -1 리턴
if len(food)==0: return -1
n, t = food.pop(0) # 번호, 시간
# 음식 먹고 남은 시간이 0이 아니면
if t-1!=0: food.append([n,t-1])
if len(food)==0: return -1
# 네트워크 복구 후 먹을 음식
num, time = food.pop(0)
return num개인적으로 그리디가 쥐약이다. 신박한 수학적인 풀이가 요구되서 효율적인 알고리즘 세우기 어려워.. 아직 코테의 길은 멀었다. 공부하자 ^^
