무지의 먹방 라이브(python)

문제 설명

무지가 회전판을 이용해서 먹방을 한다. 한참 먹방을 하던 도중 갑자기 네트워크 장애가 발생했다고 하자. 그렇다면 무지는 네트워크가 다시 정상화 될 때 몇 번째의 음식부터 먹어야 할까? 참고로 말하자면 효율성 테스트가 존재하는 문제다.

 

더 자세한 설명, https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=python3 

프로그래머스

 

문제 풀이

첫 번째 접근

처음에는 그냥 큐에 넣고 돌려서 계산하는 방법을 떠올렸다. 그러나 효율성 테스트에는 무려 food_times의 원소가 최대 100,000,000이라 가볍게 포기했다.

 

왜 그리디 문제일까?

해당 문제를 소개한 책에 분류된 카테고리로 보면 그리디 문제라고 나와있다. 그런데 당시 내가 생각한 그리디 문제는 주어진 데이터 중에 최대 값(혹은 최소 값)을 찾고 그 다음 최대 값을 찾고... 이런 종류 뿐이었다. 이 문제의 경우 데이터인 음식을 1부터 차례로 먹어야 하는데, 어디에서 그리디가 쓰일까?

바로 계산 시간을 줄이는데 그리디가 쓰인다. 

두 번째 접근

시간 K에서 다 먹을 수 있는 음식을 먼저 빼준다. 이때는 약간의 수식이 필요하다. 이렇게 전부 해주고 나면 k 시간 동안 먹을 수 있는 음식은 전부 제거된다. 그리고 마지막으로 남은 음식 중 몇 처음으로 먹어야 하는 음식을 계산해주면된다.

 

1. 일단 음식 먹는 시간을 전부 더해서 이것이 k보다 작으면 -1을 반환한다. 왜냐하면 k라는 시간 안에 모든 음식을 먹을 수 있기 때문이다.

2. 음식 시간과, 음식 번호로 우선순위 큐(최소 힙)에 넣어준다.

3. 그리고 '음식을 먹는 데 사용한 시간 + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식의 수'가 k보다 작거나 같을 때까지 반복문을 반환한다. 이때 (현재의 음식 시간 - 이전 음식 시간)을 구해주는 이유는 이전 음식은 전부 먹었다로 가정하기 때문에 이전 음식을 먹을 때마다 현재의 음식 시간도 같이 줄어들기 때문이다. 

예를 들어서 이전 음식 시간이 3이고 현재 음식 시간이 8이라고 해보자. 그렇다면 이전 음식 시간을 3만큼 먹었을 때 현재 음식 또한 3만큼 먹었기 때문이다.

4. 반복문 안에서는 우선 순위 큐에서 값을 하나 빼주고 '(현재 음식 시간 - 이전 음식 시간) * 길이'를 지금까지 음식을 먹은 시간에 더해준다. 그리고 음식 하나를 먹었으므로 길이를 하나 뺀다. 마지막으로 현재 음식 시간을 이전 음식 시간에 넣어 변수를 조정해주면 된다.

5. 위의 반복문을 전부 돌아주었으면 이제는 인덱스 별로 음식을 정렬한다.

6. 마지막으로 k에다가 지금까지 먹은 음식 시간을 빼줘서 남은 k를 구한 뒤에 이것을 길이로 나눈 나머지를 구해 첫 번째로 먹어야할 값을 조정한다. 예를 들어 k가 5일때 길이가 2라면 첫 번째 음식부터 다시 먹어야 한다는 의미이다. 이렇게 조정해서 나온 값의 번호를 반환하면 된다.  

코드

파이썬

import heapq

def solution(food_times, k):
    answer = 0
    
    # 전체 음식을 먹는 시간이 방송이 중단된 시간보다 작다면 -1
    if sum(food_times) <= k:
        return -1
    
    q = []
    for i in range(len(food_times)):
        heapq.heappush(q, (food_times[i], i + 1))
    
    sum_value = 0
    previous = 0
    length = len(food_times)
    
    # K안에 전부 먹을 수 있는 음식을 먼저 계산해서 시간을 줄인다 -> 그리디
    # 음식을 다 먹는 시간 * 남은 음식의 개수
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1
        previous = now
    
    result = sorted(q, key=lambda x: x[1])
    return result[(k - sum_value) % length][1]