이코테-chapter11: 그리디 문제-무지의 먹방 라이브
코드
# https://programmers.co.kr/learn/courses/30/lessons/42891
# 난이도: 하, 메모리 제한: 128MB, 2019 카카오 신입 공채
import heapq
import sys
input = sys.stdin.readline
def solution(food_times: list, k: int) -> int:
# 전체 음식을 먹는 시간보다 k가 크거나 같다면 -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) # 남은 음식의 개수
# 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]
if __name__ == '__main__':
print(solution([3, 1, 2], 5)) # 1
출처 & 깃허브
programmers 무지의 먹방 라이브
이것이 취업을 위한 코딩 테스트다 with python
github
Author And Source
이 문제에 관하여(이코테-chapter11: 그리디 문제-무지의 먹방 라이브), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cosmos/이코테-chapter11-그리디-문제-무지의-먹방-라이브-9nle3lu9저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)