[BOJ/백준][Gold3] 12764 : 싸지방에 간 준하 (C++)

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

12764번: 싸지방에 간 준하

 

 

[난이도] Gold3
[유형] 시뮬레이션

[풀이]
set 2개를 이용해 현재 빈자리와 현재 사용중인 자리를 저장해주면서
시뮬레이션을 해주었습니다. 삽입/삭제를 O(logN)에 할 수 있도록 set을 이용하였습니다.
우선순위 큐를 이용하여도 됩니다.

 

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int N,pos[100001],cnt[100001];
vector<pair<int,int>> v;
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        int s,e;
        scanf("%d%d",&s,&e);
        v.push_back({s,i});
        v.push_back({e,i});
    }
    set<int> empty,use;
    sort(v.begin(),v.end());
    for(auto [t,i] : v){
        if(pos[i]){
            use.erase(pos[i]);
            empty.insert(pos[i]);
        }else{
            if(empty.size()>0){
                pos[i]=*empty.begin();
                empty.erase(pos[i]);
            }else if(use.size()>0){
                pos[i]=*(--use.end())+1;
            }else{
                pos[i]=1;
            }
            use.insert(pos[i]);
            cnt[pos[i]]++;
        }
    }
    vector<int> ans;
    for(int i=1;;i++){
        if(!cnt[i]) break;
        ans.push_back(cnt[i]);
    }
    printf("%d\n",ans.size());
    for(auto a : ans) printf("%d ",a

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/12764.cpp