BOJ 12764 : 싸지방에 간 준하

• 문제 링크 : boj.kr/12764
• 난이도 : G3
• 태그 : 시뮬레이션, 우선순위 큐

12764번: 싸지방에 간 준하

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    vector<pii> arr(n);
    vector<int> cnt(n+1);
    priority_queue<pii, vector<pii>, greater<pii>> _pq;
    priority_queue<int, vector<int>, greater<int>> _seat;
    for(int i = 1; i <= n; i++) {
        _seat.push(i);
    }
    for(int i = 0; i < n; i++) {
        cin >> arr[i].first >> arr[i].second;
    }
    sort(all(arr));
    int ans = 0;
    for(int i = 0; i < n; i++) {
        while(!_pq.empty()) {
            if(_pq.top().first < arr[i].first) {
                _seat.push(_pq.top().second);
                _pq.pop();
            }
            else {
                break;
            }
        }
        int t = _seat.top();
        _pq.push({arr[i].second, t});
        ans = max(ans, t);
        cnt[t]++;
        _seat.pop();
    }
    cout << ans << "\n";
    for(int i = 1; i <= ans; i++) {
        cout << cnt[i] << " ";
    }

    return 0;
}

---

풀이

어떤 사람이 싸지방에 들어왔을 때, 1. 가장 먼저 끝나는 사람, 2. 가장 낮은 번호의 좌석 두 가지를 확인하면 된다.

우선순위 큐를 활용하면 각각에 대해 logn으로 관리할 수 있다.