그리디 기출 문제 06 무지의 먹방 라이브

• 회전판 위 N 개의 음식
• 각 음식은 1 ~ N 까지의 번호
• 각 음식 섭취에는 일정 시간 소요

다음의 방법으로 음식 섭취

1. 무지는 1번 음식부터 먹는다. 회전판 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.

2. 마지막 번호의 음식 섭취 후 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.

3. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취 (다음 음식이란 아직 남은 음식 중 가장 가까운 번호의 음식)

4. 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다.

 

import sys 
input = sys.stdin.readline 

food_times = list(map(int,input().split()))
k = int(input())

n = len(food_times)
tmp = 0 

for i in range(k):
    if food_times[(i+tmp)%n] == 0 :
        tmp += 1 
    food_times[(i+tmp)%n] -= 1 

print(food_times)
print((i+tmp+1)%n +1)

 

간단하게 음식 섭취 시간 리스트를 돌며 답을 구했는데, 정답지는 다른 답을 요구한다. 

 

food_times 의 길이가 1 이상 200,000 이하이고 

원소의 개수는 

1이상 100,000,000 이하의 자연수, 

그리고 k는 

1이상 2 x 10의 13 승 이하의 자연수 라는 것을 고려하자. 

 

그냥 brute force 로 도는 것은 시간적으로 문제가 있다. 

작은걸 먼저 처리해야 하지 않을까 라는 생각은 했지만 구체적인 알고리즘까지는 잘 연결되지 않았다. 

 

문제 풀이를 위한 알고리즘은 다음과 같다. 

먼저 음식 섭취 시간에 따라 우선순위 queue 에 넣는다. 

넣을 때는 (섭취 시간, 순서) 로 넣는다. 

 

그 후 우선 순위 queue 에서 첫번째 즉 가장 작은 시간이 걸리는 원소를 뽑아내고 전체 음식 개수를 곱한다. 

예를 들어 3 이 가장 작은 시간이라하고 전체 음식 개수가 5개라 할 때 가장 작은 시간이 0 되는 기점은 3 X 5 = 15 만큼 지난 시점이라는 것을 알 수 있다. 

K 값에 따라 다르지만 만약 K 값이 굉장이 큰 경우, 다음과 같이 접근을 해야 문제 풀이가 가능하다. 

K 값이 작은 경우 예를 들어 4정도라고 생각해보자. 그 때는 간단한 문제이므로 나열식으로 하나씩 접근하면 어려울 것이 없다. 

 

참고한 코드 구현은 다음과 같다. 

import sys 
input = sys.stdin.readline 
import heapq
food_times = list(map(int,input().split()))
K = int(input())
heap = []

for i in range(1, len(food_times)):
    heapq.heappush(heap, (food_times[i-1] , i))

n = 0
tmp = 0



while(heap):
    t, idx = heapq.heappop(heap)
    if K - t * len(heap)+1 >= 0:
        K -= t * len(heap)+1
        food_times = [i - K for i in food_times]
    else:
        for i in food_times:
            if i == 0:
                continue
            else:
                tmp += 1 
        tmp = tmp % (len(heap))
        break 

print(tmp+1)

 

정답지의 구현 방식을 한번 참고해본다. 

 

우선 전체 음식을 먹는 시간보다 k 가 크거나 같은 경우의 처리이다. 

if sum(food_times) <= k:
	return -1

queue 에서 빼서 줄인 음식 시간 만큼 다른 음식 시간에서도 빼줘야 한다. 

위 구현에서는 이 부분을 실수로 반영하지 않았다. 

이와 같은 실수를 하지 않기 위해서는 구현 전에 아이디어를 명확하게 잡고 시작해야한다. 

 

sum_value = 0 # 먹기 위해 사용한 시간
previous = 0 # 직전에 다 먹은 음식 시간 


length = len(food_times)

while sum_value + (heap[0][0] - previous) * length <= K: 
    now = heapq.heappop(heap)[0]
    sum_value = (now - previous) * length 
    length -= 1
    previous = now

해당의 경우 K 변수를 건드리지 않기 위해서 sum_value 라는 변수를 사용했다. 

또한 length 변수를 사용했다. 하지만 sum_value 는 K 로 대체 가능하고, len(heap)이 length 변수를 대체할 수 있다. 

코드를 더 정리해보자면 아래와 같다. 

 

while K - heap[0][0] * len(heap) > 0:
    tmp = heapq.heappop(heap)[0]
    K -= (tmp - previous) * (len(heap)+1) 
    previous = tmp

 

또한 최종 나열을 위해서 내 구현과 같이 복잡하게 for 문을 돌 필요가 없다. 

heap.sort(key = lambda x: x[1])
print(heap[(K-1) % len(heap)][1])

0인 경우 뛰어넘는다는 뜻은 해당 값을 빼버리면 된다는 뜻이다. 

즉 idx 를 기준으로 sort 해주면 해결된다. 

for 문을 도는게 조금 더 빠를 수 있지만, 어차피 몇개 안되기 때문에 sort 를 쓰는 것이 깔끔하다. 

 

※여기서는 왜 sort대신 heap sort 를 사용할까?

https://stackoverflow.com/questions/24666602/python-heapq-vs-sorted-complexity-and-performance

Python heapq vs. sorted complexity and performance

 

The heapq is faster than sorted in case if you need to add elements on the fly i.e. additions and insertions could come in unspecified order. Adding new element preserving inner order in any heap is faster than resorting array after each insertion.

 

The sorted is faster if you will need to retrieve all elements in order later.

 

즉 정렬 된 list 에 새로운 원소를 집어넣는 경우 heap 은 넣기만 하면 되는데 sort 는 다시 sort 를 사용해야 하므로 더 오래 걸린다. 

해당 문제는 반복해서 sort 를 할 필요는 없으므로 그냥 sort 를 쓰는 것이 우선순위 큐를 쓰는 것보다 빠를 수 있다.