백준 12764번 싸지방에 간 준하 (GG)

문제

현재 대한민국 해군에 소속되어있는 준하는 문제를 풀기 위해 매일같이 사이버 지식 정보방 통칭 싸지방에 다닌다. 그러나 최근 문제가 생겼다. 싸지방에 사람이 몰려 컴퓨터 수가 모자라게 된 것이다. 이런 사태를 도저히 용납할 수 없었던 준하는 곧 전역하는 선임을 설득해 민원을 넣도록 하는 데 성공했다.

마침내 부대에서는 민원을 받아들이기로 하였고, 컴퓨터를 증설하기로 했다. 또한, 컴퓨터 간의 사용률에 따라 다른 성능의 컴퓨터를 설치하고자 한다.

하지만 예산이 부족해 사람 수 만큼 컴퓨터를 살 수가 없었다. 고심에 고심을 거듭한 준하는 모든 사람이 항상 정해진 시간에 싸지방을 이용한다는 사실을 발견했다.

컴퓨터가 있는 자리에는 1번부터 순서대로 번호가 매겨져 있다. 모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이다.

준하가 발견한 사실과 이용 규칙을 가지고, 모든 사람이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하시오.

입력

첫째 줄에 사람의 수를 나타내는 N이 주어진다. (1≤N≤100,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 P와 종료 시각 Q가 주어진다. (0≤P<Q≤1,000,000)

시작 시각이나 종료 시각이 다른 사람과 겹치는 경우는 없다.

출력

첫째 줄에 사람이 모든 사람이 기다리지 않아도 되는 컴퓨터의 최소 개수 X를 출력한다.

둘째 줄에는 1번 자리부터 X번 자리까지 순서대로 각 자리를 사용한 사람의 수를 띄어쓰기 간격으로 출력한다.

 

 

<내코드>

union find도 좀 쓰고, nlogn 방식으로 풀려고 했으니 fail

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
 
int parent[100001];
 
int findparent(int node)
{
    
    if(parent[node] == node)
    return node;
    
    return parent[node] = findparent(parent[node]);
}
 
void merge(int x, int y)
{
    
    
    int nodex = findparent(x);
    int nodey = findparent(y);
    
    parent[nodex] = nodey;
}
 
 
struct time{
    
    
    int start;
    int end;
    
    
    bool operator<(const time &t)
    {
        return start < t.start;
    }
};
 
 
 
time computer[100001];
int countx[100001];
 
 
int main(void)
{
    
    
    
    
    int N;
    cin >> N;
    vector<time> vec;
    
    for(int i = 1; i<=N; i++)
    {
        
        
        int start , end;
        
        cin >> start >> end;
        parent[i] = i;
        vec.push_back({start,end});
        
        
        
        
    }
    
    sort(vec.begin(),vec.end());
 
    for(int i = 0; i<N; i++)
    computer[i+1] = vec[i];
    
    
    
    for(int i = 1; i<=N; i++)
    {
        countx[findparent(i)]++;
        
        for(int j = i+1; j<=N; j++)
        {
            if(computer[i].end <= computer[j].start )
            {
                merge(j,i);
                break;
            }
        }
    }
    
    
    int result = 0;
    
    for(int i = 1; i<=N; i++)
    {
        if(countx[i])
        result++;
    }
    cout<<result<<endl;
    
    for(int i = 1; i<=N; i++)
    {
        if(countx[i])
        {
            cout<<countx[i]<<" ";
        }
    }
    
 
    
    
    
 
    
    

 

 

 

<정답>

이해 안되는 부분이 많다. 반드시 set을 써야 맞는 이유가 뭘까,,,,?

전체적인 개념은 자리 하나하나에 대해 보자는 것이다.

1) 정렬해서 가장 빨리 시작한 사람을 push시키고 그 때 좌석 0을 지정한다.

2) 그리고 그 다음사람에서는 현재 앉아있는 사람과 비교해서 자신의 시작시간이 현재 앉아 있는 사람의 

종료시간보다 크다면 현재 앉아 있는 자리에 자기가 앉는 개념. 그러므로 기존 우선순위 큐를 pop시키고 

save에 현재 앉아 있는 좌석을 넣어준다.

그 다음 사람이 왔을 때 또 현재 앉아있는 사람보다 시작시간이 크다면 같은 동작 반복하고 아니라면

무시한다.

그리고 save는 현재 앉아있는 사람의 종료시간보다 시작시간이 큰 경우에만 insert되고 그경우에 그 자리와 

end값이 다시 push되며 save는 지워진다.

따라서 save가 존재 한다는 것은  같은 좌석에 대한 작업이라는 뜻.

#include <iostream>
 
#include <vector>
 
#include <algorithm>
 
#include <queue>
 
#include <set>
 
#include <functional>
 
using namespace std;
 
 
 
const int MAX = 100000;
 
 
 
int N;
 
pair<int, int> arr[MAX];
 
set<int> save; //자동 정렬
 
int result[MAX];
 
 
 
int solve()
 
{
 
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; //minHeap
 
        int seat = 0; //컴퓨터 좌석
 
 
 
        for (int i = 0; i < N; i++)
 
        {
 
                 while (!pq.empty())
 
                 {
 
                         //현재 시작 시간보다 빠른 사람들 pop
 
                         if (pq.top().first <= arr[i].first)
 
                         {
 
                                 save.insert(pq.top().second);
 
                                 pq.pop();
 
                         }
 
                         else
 
                                 break;
 
                 }
 
                 //남는 자리 없는 경우: 다음 번호의 컴퓨터를 준다
 
                 if (save.empty())
 
                 {
 
                         pq.push({ arr[i].second, seat });
 
                         result[seat]++;
 
                         seat++;
 
                 }
 
                 //set의 첫 번째 원소를 자리로 배정
 
                 else
 
                 {
 
                         set<int>::iterator idx = save.begin();
 
                         pq.push({ arr[i].second, *idx });
 
                         result[*idx]++;
 
                         save.erase(idx);
 
                 }
 
        }
 
       
 
        return seat;
 
}
 
 
 
int main()
 
{
 
        ios_base::sync_with_stdio(0);
 
        cin.tie(0);
 
        cin >> N;
 
 
 
        for (int i = 0; i < N; i++)
 
                 cin >> arr[i].first >> arr[i].second;
 
        sort(arr, arr + N);
 
 
 
        int seat = solve();
 
        cout << seat << "\n";
 
        for (int i = 0; i < seat; i++)
 
                 cout << result[i] << " ";
 
        cout << "\n";
 
 
 
        return 0;
 
 
 
}