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

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

1966번: 프린터 큐

풀이

queue와 priority_queue를 사용하여 푸는 문제다.

 

예제 입력의 마지막 테스트 케이스를 예로 들면,

6 0 1 1 9 1 1 1

이므로 6개의 문서 중요도 중 0번째에 위치한 1의 출력 순서가 몇 번째인지를 출력하면 된다.

해당 문서의 중요도 뿐 만 아니라 위치(index값)도 고려해야하기 때문에, 큐에 구조체를 사용해서 중요도와 index를 함께 저장할 것이다.

큐에 구조체를 쓸 생각을 못해서 풀이 시간이 오래 걸렸다....

 

먼저 우선순위 큐를 사용하여 중요도를 내림차순으로 정렬한다.

9 1 1 1 1 1

 

큐에는 index와 중요도가 함께 저장된다.

index: 0 1 2 3 4 5

importance: 1 1 9 1 1 1

 

큐와 우선순위 큐의 맨 앞 값을 비교하여 일치하지 않을 경우 큐의 front 값을 pop하여 뒤로 push한다.

1 9 1 1 1 1

9 1 1 1 1 1

위와 같이 정렬 되어 큐와 우선순위 큐의 맨 앞 값이 9로 일치하면, pop해준다. 

1이 출력될 때까지 반복한다.

 

코드

#include <iostream>
#include <queue>

using namespace std;

struct st {
    int index;  //몇 번째인지 저장
    int importance;    //중요도 저장
};

int main() {
    int t; scanf("%d", &t);  //테스트 케이스 개수
    for (int i = 0; i < t; i++) {
        int N, M; scanf("%d %d", &N, &M);    //N: 문서 개수, M: 몇 번째로 인쇄되었는지 궁금한 문서가 놓인 위치(맨 왼쪽 0)

        priority_queue<int> p_q;    //내림차순 정렬
        queue<st> q, turn_q, turn;      //q: 숫자 저장, turn_q: 찾고자하는 문서 위치를 turn에 저장하기 위한 큐, turn: 찾고자 하는 문서의 index와 importance 저장

        for (int i = 0; i < N; i++) {
            int I; scanf("%d", &I);     //I: 중요도
            q.push({i, I});
            turn_q.push({i, I});
            p_q.push(I);
        }

        for (int i = 0; i < M; i++) {
            turn_q.push(q.front());
            turn_q.pop();
        }
        turn.push(turn_q.front());

        int count = 0;
        while(!q.empty()) {
            if (q.front().importance == p_q.top()) {
                if (q.front().index == turn.front().index) {
                    printf("%d\n", count + 1);
                    break;
                }
                else {
                    count++;
                    q.pop();   
                    p_q.pop(); 
                }
            }
            else {
                q.push(q.front());
                q.pop();
            }
        }
    }
}