백준 - 12764 싸지방에 간 준하

문제

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

12764번: 싸지방에 간 준하

모든 사람은 비어있는 자리 중 번호가 가장 작은 자리에 앉아야 한다.

다음과 같은 이용 규칙으로 모든 사람이 기다리지 않는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하는 문제였다.

 

문제 풀이

처음에 비어있는 자리 중 번호가 가장 작은 자리에 앉는다는 규칙을 제대로 보지 않아서 틀렸었다. 해당 규칙을 지키도록 로직을 수정해 맞을 수 있었다.

 

먼저 시작 시각을 기준으로 오름차순 정렬을 했다. 그후 모든 사람을 PQ에 넣으면서 각 자리를 비우고 채우는 과정을 반복해 각 자리의 사람 수를 구할 수 있었다.

 

PQ는 해당 자리의 종료 시간을 저장한 pair PQ와 빈 자리 번호를 저장한 PQ 2개를 사용했다.

 

해당 과정은 다음과 같이 진행했다.

1. 현재 시작 시각보다 종료 시간이 빠른 자리를 모두 비운다.

해당 자리의 번호를 빈 자리 번호 pq에 저장한다. 이때 pq를 사용했기 때문에 오름차순으로 정렬된다.

 

2. 빈 자리가 있다면 해당 자리에 넣는다.

현재 종료 시간과 해당 자리 번호를 pq에 넣어주고 빈 자리 pq에서 해당 자리 번호를 빼준다.

 

3. 빈 자리가 없다면 맨 뒤에 넣는다.

빈 자리 pq가 비어있다면 pq에 현재 종료 시간과 컴퓨터 배열의 크기를 저장한 comSize를 함께 넣어준 후 comSize를 1 늘려준다.

 

자리에 넣을 때마다 computer 배열의 해당 자리 index 값을 1 늘려줘 몇 명의 사람이 사용했는지를 구할 수 있었다.

/*
1. 시작 시각 기준 오름차순 정렬
2. PQ 사용, {종료 시간, computer num} 해당 num에 넣을 때마다 ++
3. 빈 자리 중 컴퓨터 번호 가장 작은 자리에 앉는 것이 규칙
- pq에 빈 번호 저장
*/

int N;
vector<pair<int, int>> arr;
vector<int> computer;
priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; //종료 시간, computer num
priority_queue<int, vector<int>, greater<int>> numPq; //빈자리
int comSize = 0;

int main() {

	scanf("%d", &N);

	arr = vector<pair<int, int>>(N);
	computer = vector<int>(N, 0);

	
	for (int i = 0; i < N; i++) {
		int s, e;
		scanf("%d %d", &s, &e);
		arr[i] = { s,e };
	}

	sort(arr.begin(), arr.end());

	for (int i = 0; i < N; i++) {
		
		
		int nowStartTime = arr[i].first;
		int nowEndTime = arr[i].second;

		//1. 현재 시작 시각보다 빠른 종료 시간 가진 자리 비우기
		while (!pq.empty() && pq.top().first < nowStartTime) {
			numPq.push(pq.top().second);
			pq.pop();
		}
		//2. 빈 자리가 있다면 바로 넣기
		if (!numPq.empty()) {
			int n = numPq.top();
			numPq.pop();
			pq.push({ nowEndTime, n });
			computer[n]++;
		
		}
		//3. 빈 자리가 없다면 맨 뒤에 넣기
		else {
			pq.push({ nowEndTime, comSize });
			computer[comSize]++;
			comSize++;
		}
	
	}

	printf("%d\n", comSize);
	for (int i = 0; i < comSize; i++) {
		printf("%d ", computer[i]);
	}

	return 0;
}

/*

*/