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

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

1966번: 프린터 큐

풀이 : 

- 0부터 n전까지 문서가 요청이 되고, 각 문서별로 중요도가 정해져있다.

- 현재 출력하려고 하는 문서보다 중요도가 더 높은 문서가 뒤에 있다면,

   문서를 뒤로 재배치 하고, 그렇지 않다면 출력한다.

-  그렇게 할 때, m인덱스의 문서는 몇 번째로 출력이 되는지 구하는 문제이다.

- 재배치 과정에서 인덱스가 바뀌기 때문에 인덱스를 저장할 필요가 있다.

- 중요도와 같이 저장할 수 있도록 queue는 pair로 선언한다

- 중요도는 중복이 될 수 있기 때문에 갯수를 세어줄 배열도 선언해준다

- 출력하기 전, 중요도 배열을 탐색하여, 출력 할지 말지를 결정해준다.

 

코드 :

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int t, n, m, num, cnt, arr[15];
    queue<pair<int, int>> q; //중요도와 인덱스를 같이 저장하기 위해 pair로 선언
    bool swapit; //뒤에 재배치 할 지의 여부를 저장

    cin >> t;
    while(t--){
        for(int i = 1; i < 10; i++){
            arr[i] = 0; //중요도 갯수 들어갈 배열 초기화
        }
        cnt = 0;
        cin >> n >> m;
        for(int i = 0; i < n; i++){
            cin >> num;
            q.push({num, i}); //중요도와 인덱스 값 큐에 저장
            arr[num]++; //중요도 갯수 카운트
        }
        while(!q.empty()){ //큐가 빌 때까지 while문을 돌려준다
            swapit = false;
            for(int i = 1; i < 10; i++){ //뒤에 있는 문서 중 중요도가 더 높은 문서가 있는지 체크
                if(i == q.front().first){ 
                    arr[i]--; //현재 문서의 중요도 갯수는 일단 마이너스
                }else if(arr[i] > 0 && i > q.front().first){ //더 높은 중요도를 찾은 경우
                    swapit = true; //재배치 해야 함을 저장하고 바로 나간다
                    break;
                }
            }
            if(swapit){ //재배치 해야 한다면
                q.push(q.front()); //현재의 문서를 가장 뒤로 재배치
                arr[q.front().first]++; //중요도 갯수를 미리 빼줬었기 때문에 다시 하나 올려준다
            }else{ //재배치 하지 않고 인쇄해야 한다면
                cnt++; //몇 번째 인쇄하는지 카운트
                if(q.front().second == m){ //인쇄하려는 문서의 인덱스 값이 m과 같다면
                    cout << cnt << '\n'; //카운트 했던 cnt 출력하고
                    while(!q.empty()){ //큐에 남아 있는 것은 다 pop해서 비워준다
                        q.pop();
                    }
                    break;
                }
            }
            q.pop(); //while문 한 번 돌 때마다 pop해준다
        }
    }
}