[BOJ 27660 // C++] Queue skipping (Hard)

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 27660번 문제인 Queue skipping (Hard)이다.
문제는 아래 링크를 확인하자.

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

27660번: Queue skipping (Hard)

먼저 현재의 대기열의 상태를 큐 자료구조를 이용해 나타내자. 이 때 queue의 front가 줄의 맨 뒤이고 back이 줄의 맨 앞이 되게끔 관리할 것이다.

 

이제, 큐에서 자리를 옮기는 사람이 나타날 때마다 해당 사람이 자리를 이동한 횟수를 1 늘리고 큐의 back에 해당 사람을 추가해주자. 이런 기록을 남겨두면 매 사람이 자리를 이동할 때마다 전체 줄을 새로 기록하는 대신 모든 기록을 다 읽은 뒤 queue의 front 원소들을 꺼내보면서 더 이상 해당 기록에 대응되는 위치에 있지 않은 자료를 순차적으로 제거해나가는 방식으로 최종 대기열을 구해낼 수 있게 된다. 구체적으로, queue의 front에 있는 사람의 "자리를 이동한 횟수"가 남아있다면 지금의 차례가 아닌 아직 queue에 남아있을 위치가 해당 사람의 위치(후보)가 될 것임을 알 수 있다. 따라서 이러한 경우 해당 사람의 줄을 롬긴 횟수를 1 줄이고 pop하고, 그렇지 않은 경우 그 사람이 남은 사람들 중 줄의 맨 뒤에 서있는 것으로 처리하는 작업을 반복하는 것으로 문제를 해결할 수 있다.

 

이 작업은 굳이 queue 자료구조를 이용하지 않고 길이 20만의 배열을 이용해도 충분히 해결할 수 있을 것이다. 원리는 동일하다.

 

아래는 제출한 소스코드이다.

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

int T, N, E;
int cnt[100001];

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

	cin >> T;
	while (T--) {
		memset(cnt, 0, sizeof(cnt));
		queue<int> que;
		cin >> N >> E;
		
		for (int i = N; i > 0; i--) que.push(i);
		while (E--) {
			int x; cin >> x;
			cnt[x]++, que.push(x);
		}

		while (cnt[que.front()]) {
			cnt[que.front()]--;
			que.pop();
		}

		cout << que.front() << '\n';
	}
}