BOJ 12764 : 싸지방에 간 준하

문제링크

풀이요약

그리디, 우선순위 큐

풀이상세

1. 최소 2개의 priority_queue가 필요하다. 나의 경우, 진입을 위한 정렬을 위해 3개의 priority_queue를 활용했다.

   • 빈자리가 나올 경우 저장할 용도의 pq
   • 끝나는 시간과 현재 앉는 자리를 정렬하는 pq

2. 또한 앉은 자리를 출력해야하므로 카운트 배열을 하나 생성하자.

3. 먼저 자리가 빌 수 있는지 확인한다. 자리가 비는 조건은 현재 입장하는 사람의 시간보다, 싸지방을 나가는 사람의 시간이 더 적은 경우이다.

4. 누군가가 나가는 경우, 현재 앉았던 자리를 빈자리 큐에 저장하자.

5. 현재 빈자리가 남아있다면 현재 들어오는 사람은 빈자리에 앉게 되며, 그렇지 않은 경우는 자리를 늘려서 앉히게 하자.

6. 빈자리 큐 혹은 자리가 늘어나는 경우에 카운트 배열의 값을 1씩 높여주자.

배운점

• 최댓값만큼 배열을 생성하니 소모하는 메모리가 크다.
• pq_f 를 사용하지 말고, 벡터를 통해 정렬후 넣는 식으로 진행했다면 사이즈를 제어하여 메모리를 더 줄였을 것이다.

#include <iostream>
#include <queue>
#include <vector>
#define f first
#define s second
using namespace std;

const int MAX = 1e6 + 4;
int N, ans = 1, cnt[MAX];
priority_queue<pair<int, int>> pq_f;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq_s;
priority_queue<int> pq_t;

void input() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N;
    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        pq_f.push({-a, -b});
    }
}

void go() {
    // <끝나는 시간, 인덱스>
    pair<int, int> init = pq_f.top();
    pq_f.pop();
    pq_s.push({-init.s, ans});
    cnt[ans]++;
    while (!pq_f.empty()) {
        pair<int, int> curr = pq_f.top();
        pq_f.pop();

        while (!pq_s.empty() && pq_s.top().f < -curr.f) {
            pq_t.push(-pq_s.top().s);
            pq_s.pop();
        }

        if (!pq_t.empty() > 0) {
            pq_s.push({-curr.s, -pq_t.top()});
            cnt[-pq_t.top()]++;
            pq_t.pop();
        } else {
            cnt[++ans]++;
            pq_s.push({-curr.s, ans});
        }
    }
}

void output() {
    cout << ans << "\n";
    for (int i = 1; i <= ans; i++) {
        cout << cnt[i] << " ";
    }
}

int main() {
    input();
    go();
    output();
}