문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음줄에 N개 문서의 중요도가 주어지는데, 중요도는 적절한 범위의 int형으로 주어진다. 중요도가 같은 문서가 여러 개 있을 수도 있다. 위의 예는 N=4, M=0(A문서가 궁금하다면), 중요도는 2 1 4 3이 된다.

출력

각 test case에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

예제 입력/출력

코드

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;

int main() {
	int t, m, n;

	scanf("%d", &t);

	while (t--) {
		vector<int> que;
		vector<int> priority_que;
		int  cnt = 1;

		scanf("%d %d", &n, &m);
		que.resize(n);

		for (int i = 0; i < n; i++) {
			scanf("%d", &que[i]);
			priority_que.push_back(que[i]);
		}

		// 우선순위대로 내림차순 정렬
		sort(priority_que.begin(), priority_que.end(), greater<int>());

		while (true) {
			// 우선순위가 낮은 문서가 앞에 있는 경우 뒤로 보내줌
			if (priority_que.front() > que.front()) {
				// 해당 문서가 입력받은 "원하는 문서"일 경우, 인덱스를 문서의 맨 마지막으로 바꿔줌
				// 해당 문서가 원하는 문서가 아닐경우, "원하는 문서"의 인덱스를 한칸 앞당겨줌
				m = m != 0 ? m - 1 : n - 1;
				que.push_back(que.front());
				que.erase(que.begin());
			}
			// 우선순위에 맞는 문서가 앞에 있는 경우 출력
			else if (priority_que.front() == que.front()) {
				// 해당 문서가 원하는 문서가 아닐 경우, "원하는 문서"의 인덱스를 한칸 앞당겨줌
				if (m != 0) {
					m--;
					n--; // 출력으로 인해 남아있는 문서의 갯수가 줄어듬
					priority_que.erase(priority_que.begin());
					que.erase(que.begin());
					cnt++;
				}
				// 해당 문서가 입력받은 "원하는 문서"일 경우 그대로 탈출
				else {
					printf("%d\n", cnt);
					break;
				}
			}
		}

	}

	return 0;
}

풀이

위 코드의 알고리즘은 아래와 같다.

1. 입력 받은 문서를 que와 priority_que에 저장한다.
2. priority_que는 내림차순으로 정렬한다.
3. priority_que와 que의 맨 앞에 위치해 있는 문서의 우선순위를 비교한다.
4. que의 우선순위가 낮은 경우 해당 문서는 맨 뒤로 보낸다.
   • 그 문서가 “m번째 문서(출력순서를 요구하는 문서)”에 해당되는 경우, m값을 que 가장 마지막값으로 바꾼다.
   • 그렇지 않다면, “m번째 문서”의 m값을 하나 줄인다.(한칸 앞당겨짐)
5. que의 우선순위가 priority_que의 우선순위와 동일한 경우 출력한다.
   • 그 문서가 “m번째 문서”에 해당되는 경우, 그대로 출력순서를 출력한다.
   • 그렇지 않다면, 출력순서 cnt를 증가시켜주고 m값은 하나 줄인다. (한칸 앞당겨짐) 3-5번을 반복한다.

문제 풀이가 그렇게 깔끔하진 않지만, 시간내에 풀린다.
코드가 지저분해 보여서 아쉽다.