(C++) 백준 19640번 - 화장실의 규칙

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

문제

> 데카는 회사의 화장실을 이용하려고 했다. 
> 하지만 수도 시설 고장으로 회사 내의 모든 화장실 사용이 금지됐고, 사원들은 단 하나의 임시 화장실을 이용해야 했다. 

> 임시 화장실의 앞에 데카를 포함한 N명의 사원이 대기하고 있다.
> 데카는 N명의 줄에서 K + 1번째로 줄을 섰다.
> 즉, 데카보다 먼저 도착한 사람이 K명이 있다. 
> 줄이 길어지자 사장은 M개의 줄로 나눠서 대기하라 하였다.

> N명의 사원은 순서대로 M개의 줄로 나눠 섰다. 
> 기존 줄의 1번째 사원은 1번째 줄에, 2번째 사원은 2번째 줄에, ... M번째 사원은 M번째 줄에, 그리고 M + 1번째 사원은 1번째 줄의 뒤에 서는 방식이다. 

> M개의 줄로 나눠 선 것을 본 사장은 매우 흡족해하며 자리를 떠났다.

> M개의 줄의 사원들은 암묵적으로 다음의 규칙에 따라 화장실을 이용하기로 하였다.

> 선두란, 어떤 줄에서 가장 먼저 와서, 가장 앞에 선 사람을 말한다.
> M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 화장실을 이용한다.
> M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 둘 이상인 경우, 해당 선두들 중 화장실이 급한 정도 Hi가 가장 높은 선두가 화장실을 이용한다.
> M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 둘 이상이며, 해당 선두들의 화장실이 급한 정도 Hi도 모두 같다면, 해당 선두 중 줄의 번호가 가장 낮은 줄에 선 선두가 화장실을 이용한다.
> 과연 몇 명의 사원이 화장실을 이용하고 나서야 데카의 차례가 올까? 
> 매우 초조해지기 시작한 데카를 대신해 계산해주자.

접근

문제의 조건을 통해 봐야하는게 근속일수 D, 급한정도 H, 줄 번호, 몇번 째로 왔는지 이다.
각 줄마다 맨 앞에 있는 사람 중 문제의 비교 조건을 만족하는 최 선두를 찾아야한다. 이는 각 줄을 큐로 표현하고, 큐의 맨 앞의 값을 한명이 화장실로 갈 때마다 맨 앞의 사람을 갱신해서 우선순위 큐에 넣어 최 선두를 찾아내면 된다.
이떄 큐와 우선순위 큐는 앞선 D,H,줄, 번째를 타입으로 가진다.

문제해결

> 큐에서 사용할 타입 state를 구조체로 D,H,Line, No로 정의한다.
> 우선순위 큐의 정렬 기준을 문제의 조건에 맞게 cmp로 정의한다.
> 근속일수 D가 같으면 급한 정도 H로 따지는데 이때, H가 같다면 줄 번호가 더 작은 사람이 먼저온다.
> 같지 않으면 H가 더 큰 사람이 오며, D도 같지 않으면 근속일수가 더 많은 사람이 먼저 온다.
> 이제 M개의 큐를 통해 각 줄을 표현하므로 vector를 큐 타입으로 만들어 여러개의 큐를 다룬다.
> N,M,K를 입력받고 찾아야하는 K의 번호를 K+1로 잡아둔다.
> 이제 D와 H를 입력받으며 각각의 사원들의 들어온 순서인 i를 줄 번호로 변환해 해당 줄의 큐에 넣어 줄을 세운다.
> 우선순위 큐를 선언해주고 초기값으로 각 줄, 즉 큐의 맨 front()값들을 넣어준다.
> while문에서 최 선두로 뽑은 사람의 번호가 데카의 번호가 될 때까지 반복한다.
> 우선순위 큐의 최 선두의 사람을 뽑아와서 줄번호, 번호를 저장해둔다.
> 줄 번호는 이제 그 사람과 같은 줄의 뒷사람이 앞으로 와야하므로 이를 처리하기 위해 사용한다.
> 번호는 데카인지 비교하기 위해 쓴다.
> 데카가 아니라면 rst를 증가시켜 사용한 사람의 수를 누적한다.
> 이제 줄을 앞당겨야 하므로 각 줄이 비어있는지 확인하고 안 비어있으면 앞서 pop()된 사람의 줄 번호와 같은 줄 에서 맨 앞에 있는 사람을 다시 pq에 넣는다.

코드

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

int N, M, K;
struct state {
	int D, H, Line, No;
};
struct cmp {
	bool operator()(const state& a, const state& b) {
		if (a.D == b.D) {
			if (a.H == b.H) return a.Line > b.Line;
			return a.H < b.H;
		}
		return a.D < b.D;
	}
};
vector<queue<state>> T_Line;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> M >> K;
	T_Line.resize(M + 1);
	int decaNo = K + 1;

	for (int i = 1; i <= N; i++) {
		int Line = (i - 1) % M + 1;
		int d, h;
		cin >> d >> h;
		T_Line[Line].push({ d, h, Line, i });
	}
	priority_queue<state, vector<state>, cmp> pq;
	for (int i = 1; i <= M; i++) {
		if (T_Line[i].empty()) continue;
		pq.push(T_Line[i].front());
		T_Line[i].pop();
	}
	int rst = 0;
	while (!pq.empty()) {
		int nLine = pq.top().Line;
		int nNo = pq.top().No;
		pq.pop();

		if (nNo == decaNo) break;

		rst++;

		if (!T_Line[nLine].empty()) {
			pq.push(T_Line[nLine].front());
			T_Line[nLine].pop();
		}
	}
	cout << rst << '\n';
}

후기

큐를 여러개 쓰고 싶은데 어떻게 쓸까 했는데 같은 스터디원의 리뷰를 보고 새로 알게 되었다. vector의 타입을 큐로 주면 큐를 여러개 쓸 수 있게 된다.
이번 깨달읆을 통해 문제풀이의 시각이 더 넓어졌다.