programmers Level 4 무지의 먹방 라이브

문제

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

걸린 시간

02 : 13 : 35

풀이

C++

#include <string>
#include <vector>
#include <queue>
typedef long long ll;
using namespace std;

int solution(vector<int> food_times, ll k) {
    int answer = 0;
    vector<int> empty(food_times.size(), 0);
    priority_queue<pair<int, int>> pq;
    for(int i = 0; i < food_times.size(); i++)
        pq.push(make_pair(-food_times[i], i));
    ll K = 0, T = 0; // K : 먹방이 진행된 시간, T : 전체적으로 줄어든 음식의 시간
    while(!pq.empty()){
        ll left = -pq.top().first;
        int num = pq.top().second;
        ll size = pq.size();
        left -= T;
        if(K+left*size > k) break;
        pq.pop();
        empty[num] = 1;
        if(left == 0) continue;
        K += left*size;
        T += left;
    }
    if(pq.empty()){
        answer = -1;
        return answer;
    }
    int i = 0;
    int time = (k-K)%pq.size()+1;
    while(time){
        if(!empty[i]) time--;
        i++;
    }
    answer = i;
    return answer;
}

1초씩 food_times 의 값을 줄여나가는 무식한 방법은 입력값의 범위가 큰 효율성 테스트를 통과할 수 없다. 즉, k초 후의 상태를 얼마나 빠르게 알 수 있는지가 관건이다.

회전판이 계속해서 돌며 무지 앞에 음식을 가져다 주는데 다 먹은 음식이 생겨날 경우 해당 음식을 건너뛰고 다음 음식을 섭취해야 한다.

핵심 아이디어는 이 시점을 기준으로 시간대를 나누는 것이다.

현재 회전판에 올려져 있는 음식을 차례대로 먹었을 때 제일 먼저 바닥이 나는 음식은 food_times 값이 제일 작은 번호의 음식이다.

제일 작은 food_times 의 값이 0이 될 때 까지 회전판이 돌았다고 가정하면 지나간 시간은 제일 작은 값 * 남은 음식의 개수 가 된다.

이 과정을 k초를 넘기지 않을 때 까지 반복해주면 정답은 현재 시간과, 한번 더 반복하였을 때의 시간 사이에 존재하게 된다.

구현 과정은 최소힙에 food_times 의 값을 음식의 번호와 함께 저장한 후 하나씩 꺼내어 먹방이 진행된 시간 K 와 전체적으로 줄어든 음식의 시간 T 그리고 다 먹은 음식 empty 배열을 갱신해준다. 힙에 남아있는 원소가 없다면 모든 음식을 다 먹은 것이므로 -1 를 출력한다. 그렇지 않으면 k초가 되기까지 남은 시간을 현재 남은 음식의 개수로 나누어 준 후, 남은 음식들 중에서 나머지+1(구하려는 값) 번째의 음식 번호를 정답으로 반환한다.

먹방이 진행된 시간 K 값을 갱신하는 과정에서 최대 1억 * 20만 의 곱셈이 있을 수 있으므로 산술 오버플로가 일어날 수 있음에 유의하여 관련된 변수의 자료형을 모두 long long 으로 선언해주어야 한다.