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

문제 링크

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

12764번: 싸지방에 간 준하

문제

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

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

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

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

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

입력

첫째 줄에 사람의 수를 나타내는 N이 주어진다. (1≤N≤100,000)

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

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

출력

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

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

예제 입력 1 복사

5
20 50
10 100
30 120
60 110
80 90

예제 출력 1 복사

4
1 2 1 1

알고리즘 분류

• 구현
• 시뮬레이션
• 자료 구조
• 우선순위 큐

풀이

우선 시작 시간을 기준으로 사람들의 이용 시간 정보를 정렬한다.

우선순위 큐를 사용하여 현재 이용 중인 사람들을 관리해주고, set을 사용하여 이용을 끝낸 사람들을 관리해준다.

우선순위 큐의 top이 i번째 사람의 시작 시간보다 낮다면 이용이 끝난 것이므로 pop시켜 주고 set에 insert시켜준다. 이 때 insert시키는 것은 컴퓨터의 좌석 번호이다.

set이 비어 있다면 이용이 끝난 사람들이 없다는 뜻이므로, 새로운 컴퓨터 좌석을 배치해준다.

set이 비어있지 않다면 이용이 끝난 사람이 있다는 뜻이므로, 이용이 끝나 비어 있는 좌석으로 배치해준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100005
#define INF 1e9

using namespace std;
int N;
pair<int, int> User[MAX];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
set<int> Seat; // 현재 좌석의 상태, 자동 정렬됨(BS Tree와 같은 자료구조)
int answer;
int Computer[MAX];

int Arrange() {
	int res = 0;
	for (int i = 0; i < N; i++) {
		while (!pq.empty()) {
			if (pq.top().first <= User[i].first) {
				// i번째 사람의 시작 시간보다 시작 시간이 빠른 사람들 pop
				Seat.insert(pq.top().second); // 싸지방 좌석에 앉힌다.
				pq.pop();
			}
			else break;
		};
		if (Seat.empty()) { // 남는 자리가 없으므로, 다음 번호의 컴퓨터를 부여
			pq.push(make_pair(User[i].second, res));
			Computer[res++]++;
		}
		else { // set의 첫 번째 원소가 제일 일찍 끝난 사람이므로, i번째 사람을 첫 번째 자리에 앉힌다.
			pq.push(make_pair(User[i].second, *Seat.begin()));
			Computer[*Seat.begin()]++;
			Seat.erase(Seat.begin());
		}
	}
	return res;
}

bool comp(pair<int, int> A, pair<int, int> B) {
	return (A.first < B.first);
}

int main() {
	FIRST
	cin >> N;
	for (int i = 0; i < N; i++) {
		int P, Q;
		cin >> P >> Q;
		User[i] = make_pair(P, Q);
	}
	// 사람들의 싸지방 이용 정보를 시작 시간을 기준으로 정렬한다.
	sort(User, User + N, comp);
	answer = Arrange();
	cout << answer << "\n";
	for (int i = 0; i < answer; i++) {
		cout << Computer[i] << " ";
	}
	cout << "\n";

	return 0;
}