[백준 C++] 1966 프린터큐

문제

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

현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

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

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

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

우선순위큐를 활용한 간단한 풀이도 있을건데, 필자는 문제에서 설명해준 방식대로 구현했다.

먼저, 벡터에 모든 입력값을 받고(받을때 각각중요도의 빈도수를 frequency배열로 체크), 찾고자하는 문서위치(findIndex=M), 현재문서위치(currentIndex=0)를 정의한다.
그리고 반복문을 무한번돌려서,
매회 currentIndex++;,
벡터(list)의 0번째문서를 확인,
이 문서의 중요도가 9인경우와 아닌경우로 크게 나누고,
만약 9가 아닌경우는 현재 문서의 중요도보다 큰 중요도문서가 있는경우와 아닌경우 크게 두가지로 나뉜다.
당연히 큰 중요도가있는경우 벡터(list) 0번째값을 저장후, 벡터에서 제거하고 벡터맨뒤에 새로이 추가한다.
즉,

1. 현재 문서의 중요도가 9보다작은가? (true)

   1-1. 현재 문서의 중요도 보다 더 큰 중요도인 문서가 존재하는가?
   true : list[0] 을 벡터의 맨뒤로
   -여기서 현재문서가 찾고자하는 문서의 위치라면 반복종료! (최종 res출력)
   false : 현재문서를 출력한다. (res++;)
   -여기서 현재문서가 찾고자하는 문서의 위치라면
   findIndex= list.size()-1 , currentIndex = 0; 위치를 전부 초기화및갱신

2. 현재문서의 중요도가 9인경우(1번 조건의 false)

   2-1. 현재 문서가 찾고자하는 문서의 위치라면
   현재문서를 출력후 반복문종료 (res++;)
   2-2. 현재 문서가 찾고자하는 문서의 위치가 아니라면
   현재 문서 출력만한다. (res++;)

사실 매회 list[0]에 해당하는 현재 문서의 중요도가 9인지 분류안하고 코드를 짜도 됬으나,
좀더 확실히 구분하기위하여 이를 분류하였다. (어처피 for문이 9 일때 작동안할거지만..)

전체 코드는 아래와 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int t;
	scanf("%d", &t);
	while (t--) {
		int N, M;
		vector<int> list;
		scanf("%d%d", &N, &M);
		//벡터에넣고 벡터 사이즈를 매번 갱신
		//원하는 데이터가 나올때까지 전부 구현함
		int frequency[10] = {}; //빈도수 체크
		for (int i = 0, temp; i < N; i++) { 
			scanf("%d", &temp);
			list.push_back(temp);
			frequency[temp]++;
		}
		int findIndex = M; //찾고자하는 문서위치
		int currentIndex = 0; //현재 문서 위치
		int res = 0; //출력횟수
		//printf("&&& 찾문:%d  ", findIndex);
		while (true) {
			int currentPriority = list[0]; //현재문서의 중요도
			if (currentPriority != 9) { //현재문서가 중요도9가 아닌경우
				bool cantPrint = false;
				//찾는문서보다 높은 중요도의 문서들이 있는지 확인
				for (int i = 9; i >= currentPriority + 1 ; i--) {
					if (frequency[i]) {
						cantPrint = true;
						break;
					}
				}
				//찾는문서의 위치가아니고
				if (cantPrint) { //더높은 중요도의 문서가 있는경우
					int temp = list[0];
					//맨뒤로 옮김
					list.erase(list.begin() + 0); 
					list.push_back(temp);
					//찾는문서의 위치였다면
					if (currentIndex == findIndex) {
						//찾는 문서위치 갱신
						findIndex = list.size() - 1;
						//현재 문서위치 갱신
						currentIndex = 0;
						continue;
					}
				}//찾는문서의 위치가아니고
				else { //더높은 중요도의 문서가 없는 경우
					//출력
					list.erase(list.begin() + 0); //현재 문서 삭제
					frequency[currentPriority]--; //현재 문서 빈도수 -1
					res++; //출력함
					//찾는문서의 위치였다면
					if (currentIndex == findIndex) break;
				}
			}
			else { //현재 문서 중요도가 9인경우 바로 출력가능
				//찾는문서의 위치이면
				if (currentIndex == findIndex) {
					res++;
					break; //계산끝
				}
				else {
					//출력
					list.erase(list.begin() + 0); //현재 문서 삭제
					frequency[currentPriority]--; //현재 문서 빈도수 -1
					res++; //출력함
				}
			}
			currentIndex++; //현재문서위치를 다음으로
		}
		printf("%d\n", res);
	}
}