[코테 스터디] 그리디, 무지의 먹방 라이브

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