[백준][C++] 12764 싸지방에 간 준하

www.acmicpc.net/problem/12764

12764번: 싸지방에 간 준하

 

 

 

알고리즘 종류

    - 우선순위 큐

    - 자료구조

    - 구현

 

 

 

사고 과정

    - 컴퓨터를 시작하는 시간에 따라 오름차순 정렬하고, 하나씩 뽑아서 사용중인 사용자들의 끝나는 시간과 비교한다. 비교해서 사용중인 사용자의 끝나는 시간보다 이전에 새로운 사용자가 들어오면 새로운 컴퓨터 자리를 만들어주고, 사용중인 사용자의 끝나는 시간보다 늦게 들어오면 이전 사용자의 자리를 사용하게 한다.

 

        1. 배열에 사용자의 {시작, 종료} 시간을 넣고 시작 시간에 따라 오름차순 정렬한다.

        2. 우선순위 큐에 저장된 사용자들의 종료 시간과 새롭게 들어오는 사용자의 시작시간을 비교한다.

            2-1. 우선순위 큐에 저장된 사용자들의 종료 시간보다 새롭게 들어오는 사용자의 시작시간이 더 빠르면, 새로운 자리를 마련해야 한다.

            2-2. 우선순위 큐에 저장된 사용자들의 종료 시간과 새롭게 들어오는 사용자의 시작시간이 더 느리면, 종료하고 갔기 때문에 이전에 사용한 자리의 번호를 저장해 둔다.

        3. 빈 자리를 저장하고 있는지 확인한다.

            3-1. 저장되어 있으면, 그 자리에 넣는다.

            3-2. 저장되어 있지 않으면, 새로운 자리를 만든다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int n;
vector<pair<int, int> > v;
priority_queue<pair<int, int> > pq; // 사용자의 종료 시간, 사용한 자리  
priority_queue<int> left_seats; // 빈 자리
int answer[100001]; 
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> n;
    
    int s, e;
    for(int i=0; i<n; i++){
        cin >> s >> e;
        v.push_back({s, e});
    }
    
    sort(v.begin(), v.end());
    int seat = 0;
    
    for(int i=0; i<v.size(); i++){
        
        // 다음으로 들어오는 사용자의 시작 시간과 이용중인 사용자의 끝나는 시간을 비교
        // 다음 사용자가 들어오기 전에 끝난 사용자가 있으면, 자리 번호를 저장하고 pq에서 제거  
        while(!pq.empty()){
            if(-pq.top().first <= v[i].first){
                left_seats.push(-pq.top().second);
                pq.pop();
            }
            else break;
        }
        
        // 빈 자리가 없을 때  
        if(left_seats.empty()){
            pq.push({-v[i].second, seat});
            answer[seat++]++;
        }
        // 빈 자리가 있을 때  
        else{
            int tmp_seat = -left_seats.top();
            pq.push({-v[i].second, tmp_seat});
            answer[tmp_seat]++;
            left_seats.pop();
        }
    }
    
    cout << seat << endl;
    for(int i=0; i<seat; i++)
        cout << answer[i] << " ";
        
}

 

 

 

시행착오

    - 본인에게는 굉장히 어려운 내용이었다. 그래서 이 분의 블로그를 참고하여 풀이를 했다. 

    - 이미 사용하고 있는 사용자의 종료되는 시각 VS 새롭게 들어오는 사용자의 시작 시각. 이 둘을 비교하는 것이 핵심이라고 생각한다.

    - 현재 사용자를 왜 우선순위 큐에 저장할까? 위 2개의 값을 비교해야 하는데, 우선순위 큐가 아니라면 모든 값을 순환하면서 비교해야 한다. 그러면 시간 복잡도가 n^2이 된다. 따라서 먼저 끝나는 순서대로 저장할 수 있는 우선순위 큐를 사용해서 현재 사용자들의 종료 시각을 저장하는 것이다.

    - 남는 자리도 마찬가지로 우선순위 큐를 사용한다. 가장 작은 자리 번호부터 앉히기 때문이다.