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

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

12764번: 싸지방에 간 준하

 

우선순위 큐와 구현 문제다.

 

우선순위 큐에 입력 받은 값을 넣어 오름차순으로 정렬되게끔 했다.

2차원 배열을 이용해서 컴퓨터 사용이 끝나는 시간과 몇 명이 이용했는지 저장했다.

반복문으로 컴퓨터를 사용하지 않았거나, 사용 기록이 있으나 이미 퇴실한 자리를 찾아 저장했다.

 

#include <iostream>
#include <queue>
using namespace std;

// 오름차순 우선순위 큐
priority_queue<pair<int, int>, vector <pair<int, int>>, greater<pair<int,int >>> pq;
int arr[100000][2];

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, sum = 0;	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, b;	cin >> a >> b;
		pq.push({ a, b });
	}

	for (int i = 0; i < n; i++) {
		int start = pq.top().first;
		int end = pq.top().second;
		pq.pop();

		int j = 0;

		// 비어있는 컴퓨터를 찾음 
		// [j][0]이 0이거나 값이 있어도 해당 사람의 시작 시간보다 작을 때 멈춤
		while (arr[j][0] && arr[j][0] > start) j++;

		arr[j][0] = end;
		arr[j][1]++;
	}

	// 사용한 컴퓨터 개수
	int k = 0;
	for (k; k < 100000; k++) 
		if (arr[k][1] == 0) break;

	cout << k << "\n";
	for (int i = 0; i < k; i++) cout << arr[i][1] << " ";
}

(～￣▽￣)～