백준 12764번 싸지방에 간 준하

문제 링크입니다: https://www.acmicpc.net/problem/12764

lyzqm님의 포스팅(https://lyzqm.blogspot.com/2018/01/12764.html?showComment=1542815278307#c5681124844879029471)을 참고해서 풀 수 있었던 문제였습니다.

주로 map을 사용하고 set은 사용하지 않았었는데 set이 이진탐색트리 같은 자료구조인 것을 lyzqm님의 게시글을 통해 알게 되었습니다.

알고리즘은 아래와 같습니다.

1. pair<int, int> 배열에 시작 시간과 끝나는 시간 정보를 입력합니다.

2. 시작 시간을 기준으로 정렬을 진행합니다.

3. 정렬된 순서 순으로 아래와 같이 진행합니다.

a. minHeap에 데이터가 존재한다면 현재 사람의 시작 시간보다 이른 시간에 시작한 사람들을 set에 집어넣습니다.

b. set이 비어있을 경우 남는 자리가 없는 것이므로 다음 번호의 컴퓨터를 부여합니다.

c. 반면, set이 비어있지 않을 경우 첫 번째 원소가 제일 일찍 끝난 사람이므로 현재 사람을 해당 자리에 앉힙니다.

4. 3번을 모든 사람에 대해 진행하면 최소 컴퓨터의 개수를 파악할 수 있습니다.

#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

                 {

                         auto 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;

 

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~