[프로그래머스/Level 4] 무지의 먹방 라이브

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

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

카카오 기출

 

시간이 적게 걸리는 음식부터 확인하는 그리디 접근 방식으로 해결한다. (우선순위 큐를 이용)

[3, 1, 2] 3개의 음식이 있고 k가 5초라고 가정해보자

 

1. 가장 적게 걸리는 음식인 2번 음식을 빼는데, 음식이 3개 남아 있으므로 3(남은 음식의 개수) x 1(2번 음식을 먹는 시간) = 3을 빼준다. 이는 2번 음식을 다 먹기 위해 3초가 걸린다는 의미다. 결국 전체 남은 시간은 5 - 3 = 2초가 된다.

 

2. 남은 음식중에 가장 적게 걸리는 음식은 3번 음식을 빼야하는데, 전체 음식이 2개 남아 있으므로 2(남은 음식의 개수) x 2(3번 음식을 먹는 시간) = 4를 빼줘야 한다. 그러나 현재 남은 시간이 2초인데, 이는 4보다 작으므로 빼지 않는다.

 

3. 그러므로, 다음으로 먹어야 할 음식의 번호를 찾아서 출력해야 한다. 매초 먹어야 할 음식들을 나열하고 전체 남은 시간이 2초이므로, 3번째 음식의 번호를 출력하면 된다.

(3, 1) -> (2, 3) -> (3, 1) : 1번 음식을 출력

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int solution(vector<int> food_times, long long k) {
    long long sum = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    vector<pair<int, int> > v;
    
    for(int i = 0; i < food_times.size(); i++) {
        sum += food_times[i];
    }
    
    //  전체 음식을 먹는 시간보다 k가 크거나 같다면 -1 (남은 음식이 없기 때문에)
    if(sum <= k) return -1;
    
    for(int i = 0; i < food_times.size(); i++) {
        pq.push({ food_times[i], i + 1 });
    }
    
    sum = 0; // 먹기 위해 사용한 시간     
    long long prev = 0; // 직전에 다 먹은 시간
    long long len = food_times.size(); // 남은 음식 개수
    
    // summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while(sum + (pq.top().first - prev) * len <= k) {
        int now = pq.top().first;
        pq.pop();
        sum += (now - prev) * len;
        len--; // 다 먹은 음식 제외
        prev = now; // 이전 음식 시간 재설정
    }
    
    // 우선순위 큐에 남은 값을 벡터에 옮기기
    while(!pq.empty()) {
        v.push_back({ pq.top().second, pq.top().first });
        pq.pop();
    }
    
    // 음식의 번호 순서를 기준으로 오름차순 정렬
    sort(v.begin(), v.end());
    
    return v[(k - sum) % len].first;
}