(백준) 23088번 - Aging

문제

https://www.acmicpc.net/problem/23088

풀이

프로세스들을 우선순위 큐에 넣되, aging을 일일히 구현하면 시간 초과가 발생한다.

우선순위를 $P$, 실행 요청 시각을 $R$이라고 할 때, 특정 시각 $T$에서 $i$번째 프로세스의 우선순위는 $P_i+(T-R_i)$이다. $T$는 모든 프로세스에게 동일하게 더해지므로, 우선순위 큐의 상대적 순서는 $P$와 $R$만 고려해도 무방하다. 즉, 우선순위 큐에 프로세스를 삽입할 때, $P_i$가 아니라 aging을 고려한 우선순위인 $P_i-R_i$을 넣게 되면, aging을 위해 매번 pop 및 push 연산을 수행하지 않아도 된다.

코드

#include <iostream>
#include <tuple>
#include <queue>
#include <vector>

using namespace std;
typedef tuple<int,int,int> tii;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin>>n;

    // 실행 순위: 우선순위 높음 > 실행 시간 짧음 > 먼저 등장
    vector<tii> v; // 실행 요청 시점, 초기 우선순위, 실행 시간
    for (int i=0;i<n;i++) {
        int a,b,c; // 실행 요청 시점, 초기 우선순위, 실행 시간
        cin>>a>>b>>c;
        v.push_back({a,b,c});
    }

    int curTime=0;
    int idx=0;
    priority_queue<tii> pq; // 보정된 우선순위, -실행시간, -등장 번호
    while (idx<n||!pq.empty()) {
        // 현재 시간까지 도착한 작업 pq에 삽입
        while (idx<n&&get<0>(v[idx])<=curTime) {
            pq.push({get<1>(v[idx])-get<0>(v[idx]),-get<2>(v[idx]),-(idx+1)});
            idx++;
        }

        // 처리할 작업 없는 경우
        if (pq.empty()) {
            curTime=get<0>(v[idx]);
        }
        else {
            int num=-get<2>(pq.top());
            cout<<num<<" ";
            curTime-=get<1>(pq.top());
            pq.pop();
        }
    }
}

시간복잡도

각 프로세스는 정확히 한 번 push되고 pop되므로 전체 시간복잡도는 $O(NlogN)$이다.

공간복잡도

$N$개의 프로세스를 벡터와 우선순위 큐에 저장하므로 전체 공간복잡도는 $O(N)$이다.