[그리디] 무지의 먹방 라이브

링크 : https://programmers.co.kr/learn/courses/30/lessons/42891 

코딩테스트 연습 - 무지의 먹방 라이브

만약 food_times 가 [3, 1, 2] 이고 k가 6라고 했을 때, 한번 순회하면 k는 3이 되고 [2, 0, 1] 이 된다. 다시 한번 순회한다고 했을 때 가운데 0은 건너 뛰게 되고 [1,0,0] 이 된다. 그러므로 배열 형태를 똑같이 유지한채 for문을 돌 필요가 없다. 오름차순으로 정렬해서 낮은 시간(음식 다 먹는데 적게 걸리는)부터 처리하면 된다. 책에서는 우선순위 큐를 활용한다.

 

그리고 무지가 먹방을 진행하다 food_times 값들이 모두 0이 됐는데 k 값이 남게 되면 -1을 리턴해야 된다. 하지만 꼭 먹방을 진행하다 food_times 가 다 0이 되고 k가 0보다 큰지를 확인해야만 알 수 있는게 아니다. 먹방 시작 전부터 food_times 값들을 다 더한값이 k보다 작거나 같은지 확인해서 알 수 있다.

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

 

또한 리턴 값으로 k초 후에 먹어야 할 음식의 번호를 출력해야 한다. 그러므로 우선순위 큐에 삽입할 때 (음식시간, 인덱스+1)의 튜플 형태로 삽입한다.

# 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
q = []
for i in range(len(food_times)):
	# (음식시간, 배열인덱스+1) 형태로 우선순위 큐에 삽입
	heapq.heappush(q, (food_times[i], i+1))

 

이제 본격적으로 답을 구하는 알고리즘을 알아볼 차례다.

previous 는 이전에 걸렸던 음식 시간을 담으므로써 다음번 음식에 반영시킨다.

length 는 남은 음식 갯수인데 최초 food_times 의 길이를 통해 구하고 그 뒤엔 while 돌때마다 1씩 뺀다. 즉 while 한번 돌 때마다 큐 제일 앞에 있는 음식(먹는데 가장 적게 시간이 드는 음식) 하나씩 없앤다. 

 

[8, 6, 4], k=15 인 케이스를 보고 코드를 살펴보자.

먼저 우선순위 큐를 통해 [(4,3), (6,2), (8,1)] 형태로 된다. length 는 남은 음식의 갯수인데 처음엔 배열 length(3) 로 구한다. food_times 배열 안 값이 1보다 크다는 전제가 있으므로 문제없다. 

 

가장 시간이 적게 걸리는 3번음식(4) 부터 없앤다. 3번음식(4)을 없애려면 총 12초가 필요하다. 4초 * 3(남은 음식 갯수). k는 12를 빼면서 3이 된다. 두번째는 2번음식(6) 을 없애야 하는데 이미 3번음식을 없애면서 2번음식은 2가 되어 있다. 따라서 2초 * 2(남은 음식 갯수) 이다. 그런데 4초가 필요한데 k는 3이므로 빼는 작업을 수행하지 않는다. 그래서 코드에서 while 문의 조건이 k보다 작거나 같은 때가 된다.

 

알고리즘에 의해 먼저 처리된 음식들에 쓰인 시간이 나머지 음식에게도 반영 되야 하므로 previous 변수가 필요하다. sum_value 변수를 통해 소요된 총 시간들을 저장한다. 이 값은 네트워크 장애 후 다시 시작될 음식을 찾는데 사용된다. 위에서 3번음식(4)을 없애면서 k는 3이 되고 두번째 작업은 k가 작아서 수행을 못했다. 그래서 k(3) 값과 남은 2개 값을 갖고 나머지 연산을 하면 1이므로 2번음식 부터 시작하면 된다. 

sum_value = 0 # 먹기 위해 사용한 시간
previous = 0 # 직전에 다 먹은 음식 시간
length = len(food_times) # 남은 음식의 갯수

# sum_value + (현재음식시간 - 이전음식시간) * 현재음식 개수와 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]

cf) 정렬이 전제되어 있으므로 now 값이 previous 보다 크다는게 보장된다.

 

전체 코드는 다음과 같다.

import heapq

def solution(food_times, k):
	# 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1 리턴
	if sum(food_times) <= k:
		return -1

	# 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
	q = []
	for i in range(len(food_times)):
		# (음식시간, 배열인덱스+1) 형태로 우선순위 큐에 삽입
		heapq.heappush(q, (food_times[i], i+1))

	sum_value = 0 # 먹기 위해 사용한 시간
	previous = 0 # 직전에 다 먹은 음식 시간
	length = len(food_times) # 남은 음식의 갯수

	# sum_value + (현재음식시간 - 이전음식시간) * 현재음식 개수와 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]

출처 : 이것이 코딩테스트다 나동빈 저