[BOJ 백준] 12764번 싸지방에 간 준하

문제

BOJ number : https://www.acmicpc.net/problem/12764

12764번: 싸지방에 간 준하

접근

 우선순위 큐와 set을 이용하여 자동으로 정렬이 되는 컨테이너라는 특성을 이용하여 문제를 해결할 수 있었다.

코드

#include <iostream>
#include <queue>
#include <set>

#define endl "\n"

using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pe, out;
set<int> seat;
int seatCount[100010] = {0};

int main() {
    int n, p, q, ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p >> q;
        pe.push(make_pair(p, q));
    }
    for (int i = 0; i < n; i++) {
        pair<int, int> top = pe.top();
        pe.pop();
        while (!out.empty() && out.top().first <= top.first) {
            seat.insert(out.top().second);
            out.pop();
        }
        if (seat.empty()) {
            seatCount[ans]++;
            out.push(make_pair(top.second, ans));
            ans++;
        } else {
            seatCount[*seat.begin()]++;
            out.push(make_pair(top.second, *seat.begin()));
            seat.erase(seat.begin());
        }
    }
    cout << ans << endl;
    for (int i = 0; i < ans; i++)
        cout << seatCount[i] << " ";

    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study