코딩테스트 문제 (19) - 무지의 먹방 라이브

카카오 2019 블라인드 코딩테스트 기출문제입니다.

문제

1. food_times = [3,1,2], k = 5 
=> 1
2. food_times = [8,6,4], k = 15
=> 2

풀이

효율성 테스트까지 통과해야 합니다. 일반적인 for 문을 지속적으로 돌면서 시뮬레이션 할 경우 정확성 테스트는 통과할 수 있으나 효율성 테스트는 통과할 수 없을 겁니다.

1번 케이스를 한 번 생각해보죠. 5초가 되기 전까지 1->2->3->1->3의 순으로 음식을 먹어 남아있는 음식은 1이 될겁니다. 이렇게 생각을 해보면 어떨까요? 우선 먹는 시간이 적은 음식부터 오름차순으로 (시간, 음식 index) 형태로 나열해봅시다. 그렇다면 [(1,2), (2,3), (3,1)] 이 될겁니다. 음식의 개수가 3개이기 때문에 3초 동안은 모든 음식을 먹을겁니다. 그렇다면 그 후에는 [(1,3), (2,1)] 이 될것이고 2초 동안 모든 음식을 먹었을 때, [(1,1)]이 남아 답이 1이 됩니다.

이를 일반화하면 '가장 작은 food_times * 남아있는 음식 개수' 만큼 k에서 차감하면서 차감된 시간이 k보다 커질 경우 남은 시간을 남아있는 음식으로 나눈 나머지로 처리하면 for 문을 지속적으로 처리할 필요 없이 구할 수 있습니다. 가장 작은 food_times 부터 순서대로 추출하기 위해 우선순위 큐 (heap)을 사용하겠습니다. 

kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.

홍머스 정리

난이도: 중