프로그래머스. 무지의 먹방 라이브

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

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

 

요즘 프로그래머스에서 풀었던 문제들을 다시 풀어보고 있는데 안 푼 문제가 몇개 있었고 그 중 하나다.

아마 레벨4로 되어있어서 필터링 되었나보다.

 

이 문제는 정확성과 효율성 따로 점수가 배점되어 있는데, 정확성만 놓고 보면 매우 쉽다.

k가 200만까지 이므로 그냥 벡터를 돌면서 값을 빼주고, 0이면 뛰어넘는 식으로 하나하나 탐색하면 된다.

 

정확성만 맞은 코드:

 

 

효율성 부분은 방법을 생각해 낼 수 없어서 검색해봤다.

우선 min heap인 pq를 만들고 food_times 원소들을 인덱스 번호와 함께 pair의 형태로 저장한다.

그리고 가장 작은 시간의 음식부터, 그 음식이 없어지기 까지 몇초가 지나야 하는지 계산 하면된다.

 

예를들어 food_times = {3, 1, 2}, k = 5 라면 

pq에 min heap으로 정렬하면 pq의 top은 1일 것이다.

이 1인 음식이 없어 지려면 몇초가 지나야 할까?

1 * pq.size() = 3초가 지나야 한다.

따라서 주어진 총 시간인 5초에서 3초를 빼면 2초가 남고,

pq의 top인 1은 pop으로 없애준다.

 

이제 pq = {2,3}, k = 2 인 상태다.

가장 시간이 작은 음식인 2가 없어지려면 몇초가 있어야 할까.

2 * pq.size()일까? 아니다. 

방금전에 1초인 음식을 없애기 위해 1바뀌를 이미 돌은 상태이므로 

(2-1) * pq.size() = 2 이다.

그런데 k=2에서 2를 빼면 0 이기 때문에 2초 짜리 음식은 뺄수가 없다.

 

여기서 부터는 이제 남은 음식들 중 (k % 남은 음식 갯수) 번째 음식이 답이다.

 

 

 

---

2022.04.28