[PriorityQueue] (프로그래머스 Lv 4) 무지의 먹방 라이브

문제

• 문제 링크
• 문제 설명: 1초마다 회전하는 음식판이 있다. 1번부터 N번까지 음식 번호가 증가하는 순서대로 음식을 섭취할 때, K초에 네트워크 장애가 발생한다면 네트워크 정상화 후 먹어야하는 음식의 번호를 반환하는 함수를 작성하라.
  • 음식을 모두 섭취했다면 가장 가까운 음식이 다음 대상이 된다.
  • 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
• 입력
  • food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
  • k 는 방송이 중단된 시간을 나타낸다.
  • food_times 의 길이는 1 이상 200,000 이하이다.
  • food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
  • k는 1 이상 2 x 10^13 이하의 자연수이다.

• 출력: 네트워크 정상화 후 먹어야하는 음식 번호
  • 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.

food_times	k	result
[3, 1, 2]	5	1

풀이

• food_times의 길이가 2*10^5 이기 때문에 O(N) 또는 O(NlogN) 만에 해결해야 함
• 먼저 모든 음식들을 우선순위 큐에 삽입
  • 원소 := (섭취시간, 인덱스)
  • 우선순위 큐는 가장 큰 값을 top() 으로 반환하므로 -1을 곱해서 섭취시간이 가장 작은 것을 O(1)에 얻을 수 있도록 한다.
• 섭취 시간에 대해 다음과 같은 변수를 사용
  • food_items[i] := i번째 음식이 섭취하는데 필요한 시간
  • totalTime := 지금까지 총 걸린 시간
  • t := 현재 음식 하나를 먹을 때 섭취 시간 (최초 최소 섭취 시간)
  • n := 현재 남은 음식 개수
  • tsum := 지금까지 t가 누적된 섭취 시간
• 큐에서 총 섭취 시간이 k이하이면 음식을 섭취하고 시간을 갱신
  • tsum += t; (최초 tsum = 0)
  • 섭취 시간 <= tsum 인 음식들만 섭취 
  • 1번 먹는데 걸린 시간: 현재 음식 하나를 먹을 때 섭취 시간 * 남은 음식 개수 = t * n
  • 1번 먹고난 후 시간: totalTime + (t * n)
  • t = -pq.top() - tsum; // 우선순위 큐는 가장 큰 값을 top 에 두기 때문에 -1을 곱해서 작은값을 위로
  • n = pq.size()
• 총 섭취 시간이 k 보다 크면 섭취 시간을 줄일 것
  • 섭취 시간이 이미 1이면 break
  • t = (k - totalTime) / n;
  • ㄴ 이 결과가 1보다 작으면 k == totalTime 이기 때문에 네트워크 장애가 발생한 시점이므로 break
• 남은 음식들 중 k - totalTime 번째 음식 번호를 반환
• 정답 코드

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;

int solution(vector<int> food_times, long long k) {
    priority_queue<pli> pq;
    ll n = food_times.size(); // 현재 남은 음식 개수
    ll totalTime = 0; // 지금까지 총 걸린 시간
    ll t = 1e9; // 현재 음식 하나를 먹을 때 섭취 시간
    ll tsum = 0; // 지금까지 t가 누적된 섭취 시간
    for (int i = 0; i < n; i++) {
        pq.push({-food_times[i], i+1});
        if (food_times[i] < t) t = food_times[i];
    }
    
    while (!pq.empty()) {
        if (totalTime + t * n > k) {
            if (t == 1) break;
            t = (k - totalTime) / n; // 딱 k까지 필요한 섭취 시간 구하기
            if (t < 1) break; // k == totalTime 이면 네트워크 장애가 발생하니 종료
        }
        
        tsum += t; // 시간 누적
        while (-pq.top().first <= tsum) {
            pq.pop();
            if (pq.empty()) return -1; // 이미 다먹었으면 -1
        }
        totalTime += t * n; // 총 시간 갱신
        t = -pq.top().first - tsum; // 음식 하나당 섭취 시간 갱신
        n = pq.size(); // 남은 음식 개수 갱신
    }
    
    vector<int> v;
    while(!pq.empty()) { v.push_back(pq.top().second); pq.pop(); }
    sort(v.begin(), v.end()); // 음식 번호 순으로 정렬
    return v.size() < k-totalTime ? -1 : v[k-totalTime];
}