[G3] 백준 12764번 싸지방에 간 준하 C++ 그리디 알고리즘, 우선순위 큐, 정렬, set

리뷰

 

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

다양한 자료구조를 사용하여 풀이한 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 사람의 수를 저장할 변수
• a : 각 사람의 컴퓨터 이용 시작 및 종료 시각을 저장할 배열
• c : 자리에 앉은 사람의 수를 저장할 배열

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, n개의 시작 및 종료 시간을 입력 받아 a배열을 초기화한다.
2. sort함수를 통해 a배열을 오름차순으로 정렬한다.
3. 정수형 집합 b를 초기화 하고, 0부터 n-1까지의 수를 b에 삽입한다.
4. 변수 cnt를 0으로 초기화하고, 오름차순으로 정렬할 우선순위 큐 pq를 초기화한다.
5. a배열을 순회하며 변수 st, et에 현재 요소의 시작 시간과 종료 시간을 저장한다.
6. pq가 비지 않았으면서 pq의 top()의 first가 st보다 작다면 요소를 뺴내어주고 자리 번호를 b에 삽입한다.
7. 변수 idx에 b의 begin()의 값을 저장하고, b에서 begin()을 제거한다.
8. c[idx]를 증가시키고, 증가시킨 후 값이 1이면 cnt를 증가시킨다. pq에 {et, idx}를 추가한다.
9. 모든 요소에 대한 처리 후 c의 크기와 c에 value를 공백을 기준으로 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 최악의 경우 n개의 자리가 필요하므로 set에 n개의 자리 번호를 추가해주었다. 이때 자리 번호는 중요하지 않다.
2. set을 사용하므로 자동으로 오름차순 정렬이 되어 비어있는 자리 중에서 번호가 가장 작은 자리를 찾을 수 있다.
3. 처음엔 c를 map으로 사용했지만 배열을 사용하면 메모리와 시간을 더 절약할 수 있어 변경해주었다.

 

정답 코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
using pii = pair<int, int>;

const int N = 1e5;
int n;
pii a[N];
int c[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		int p, q; cin >> p >> q;
		a[i] = { p, q };
	}
	sort(a, a + n);

	set<int> b;
	for (int i = 0; i < n; ++i) b.insert(i);

	int cnt = 0;
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	for (int i = 0; i < n; ++i) {
		int st = a[i].first, et = a[i].second;

		while (!pq.empty() && pq.top().first < st) {
			pii cur = pq.top(); pq.pop();
			b.insert(cur.second);
		}

		int idx = *b.begin();
		b.erase(b.begin());
		if (++c[idx] == 1) ++cnt;
		pq.push({ et, idx });
	}
	cout << cnt << "\n";
	for (int i = 0; i < cnt; ++i) cout << c[i] << " ";
}