[G4] 백준 19640번 화장실의 규칙 C++ 우선순위 큐, 시뮬레이션

리뷰

 

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

우선순위 큐를 활용한 신박한 문제

 

 

전역 변수

• n :  임시 화장실에 대기하고 있는 사원의 수를 저장할 변수
• m : 사장이 지시한 새로운 줄의 수를 저장할 변수
• k : 데카가 화장실에 도착했을 때 자신의 앞에 서 있던 사원의 수를 저장할 변수
• Prio : 화장실에 먼저 갈 수 있는 우선순위를 정의할 구조체

 

함수

없음

 

 

문제풀이

1. n, m, k값을 입력 받고, Prio타입 큐 벡터를 m크기로 초기화한다.
2. 변수 idx를 0으로 초기화 하고, 변수 d, h에 n명의 사원의 근무 일수와 화장실이 급한 정도를 입력 받는다.
3. q[idx]에 q, h, idx, i를 push하고, idx를 증가시킨다. 이때 idx가 m에 도달하면 idx를 0으로 변경한다.
4. Prio타입 우선순위 큐 pq를 초기화한다. m개의 큐를 순회하며 요소 한개씩을 pq에 삽입한다.
5. 변수 cnt를 0으로 초기화 하고, pq가 빌때까지 while루프를 순회한다.
6. 매 루프마다 pq에서 요소를 한개씩 꺼내 변수 d, h, qi, id에 파싱한다.
7. 기저 조건으로 id가 k인 경우 cnt를 출력한 후 조기 종료한다.
8. cnt를 증가시키고, q[qi]에서 요소를 하나 더 빼내어 pq에 삽입한다.
9. 기저 조건에 도달할때 까지 위 루프를 반복한다.

 

트러블 슈팅

1. d, h, qi만으로 데카를 식별하려 했으나 모든 값이 동일한 요소가 존재하였다.
2. 따라서 id를 구조체 내부에 추가하여 이를 통해 id가 k인 요소가 나올 경우 조기 종료처리 해주었다.

 

참고 사항

1. q가 빌때가 있으므로 꼭 empty여부를 체크해주어야 한다.
2. q는 우선순위가 아닌 선입 선출 구조이다.

 

정답 코드

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

int n, m, k;
struct Prio {
	int d, h, qi, id;
	bool operator<(const Prio& other) const {
		if (d == other.d && h == other.h) return qi > other.qi;
		if (d == other.d) return h < other.h;
		return d < other.d;
	}
};

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

	cin >> n >> m >> k;
	vector<queue<Prio>> q(m);

	int idx = 0;
	for (int i = 0; i < n; ++i) {
		int d, h; cin >> d >> h;

		q[idx].push({ d, h, idx, i });
		if (++idx == m) idx = 0;
	}

	priority_queue<Prio> pq;
	for (int i = 0; i < m; ++i) {
		if (q[i].empty()) continue;
		pq.push(q[i].front());
		q[i].pop();
	}

	int cnt = 0;
	while (!pq.empty()) {
		Prio prio = pq.top(); pq.pop();
		int d = prio.d, h = prio.h, qi = prio.qi, id = prio.id;

		if (id == k) {
			cout << cnt;
			return 0;
		}

		++cnt;
		if (!q[qi].empty()) {
			pq.push(q[qi].front());
			q[qi].pop();
		}
	}
}