[이코테] 무지의 먹방 라이브

 

프로그래머스

 

for문을 돌면서 매번 다 먹은 음식인지 아닌지 확인하며 k와 비교하는 것은 효율적이지 않다.

 

가장 빨리 먹을 수 있는 음식을 기준으로 해당 음식(가장 빠른)을 다 먹을 때마다 k초와 비교하며 남은 음식의 순서를 비교해가는 것이 핵심이다.

 

빨리 먹을 수 있는 음식은 food_times가 가장 작은 숫자다. 그리고 이 food_time이 가장 작은 순서대로 k와 비교해야하기 때문에 우선순위 큐의 내림차순을 사용했다.

 

큐에서 pop을하면서 (현재 남아 있는 음식의 양) * (현재 가장 빨리 먹을 수 있는 음식이 걸리는 시간) + 현재까지 먹방에 걸린 시간(value)를 k와 비교하며 while문을 실행한다.

 

k와 비교하며 만약 k보다 작다면 이제 음식의 순서에 따라 k초뒤에 먹을 음식을 체크할 수 있다. 이때 음식의 순서는 우선 순위 큐에 집어 넣을 때 미리 집어 넣어 줘야 한다 (음식 시간, 음식 순서)

 

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

int solution(vector<int> food_times, long long k) {
    int answer = 0;
    
    int length = food_times.size();
    priority_queue<pair<less<int>, int>> pfood_times;
    
    long long sum_time = 0;
    for(int i = 0; i < length; i++){
        sum_time += food_times[i];
        pfood_times.push(foodtimes[i], i + 1);
    }
    
    if(sum_time <= k) return - 1;
    
    int value = 0;
    int previous = 0;
    
    while(value + (pfood_times.top().first - previous) * length <= k ){
        int now = pfood_times.pop().first;
        value += (now - before) * length;
        length -= 1;
        previous = now;
    }
    
    ector<pair<int, int>> ftimes;
    while (!pfood_times.empty()) {
        ftimes.push_back(make_pair(pfood_times.top().second, -pfood_times.top().first));
        pfood_times.pop();
    }
    
    sort(ftimes.begin(), ftimes.end());
    
    answer = ftimes[k % ftimes.size()].first;
    
    return answer;
}