[백준] 1966번 프린터 큐

문제: 1966번: 프린터 큐

 

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t-- > 0) {
        int n, m; // 문서의 개수, 궁금한 문서의 현재 위치(인덱스)
        cin >> n >> m;

        // first: 인덱스, second: 중요도
        deque<pair<int, int>> docs;
        priority_queue<int> importances; // 중요도를 최대힙으로 관리

        for (int i = 0; i < n; i++) {
            int importance;
            cin >> importance;

            docs.push_back(make_pair(i, importance));
            importances.push(importance);
        }

        int cnt = 1;
        while (true) {
            int top = importances.top(); // 현재 문서들 중 가장 큰 중요도

            // 현재 deq 의 front 요소의 중요도보다 top 의 값이 더 크면 deq 의 front 요소를 맨 뒤로 보내기
            pair<int, int> cur = docs.front();
            if (cur.second < top)
                docs.push_back(cur);
            else {
                // 현재 deq 의 front 요소의 중요도가 top 보다 크거나 같다면 출력
                importances.pop(); // 이제 얘는 제거
                
                // 궁금했던 요소의 인덱스와 같다면 출력하고 while 종료
                if (cur.first == m) {
                    cout << cnt << "\n";
                    break;
                }

                cnt++; // 같지 않으면 cnt 값 +1 해주고 다시 돌아가기 
            }
            docs.pop_front();
        }
    }

    return 0;
}

 

문제 보자마자 우선 순위 큐랑 덱을 같이 쓰면 쉽게 해결할 수 있겠다는 생각이 들었다. 내가 생각한 풀이 방법은 다음과 같다.

 

1. 일단 덱에는 pair<int, int> 타입의 요소를 넣어주고, 우선 순위 큐에는 int 타입의 요소를 넣어준다.
2. 덱에서 pair 의 첫번째 요소는 인덱스, 두번째 요소는 중요도를 의미하도록 했다. 우선 순위 큐는 최대힙으로 동작하도록 했고 요소는 중요도를 의미하도록 했다.
3. 매 반복마다 최대힙에서 top 요소를 가져오는데 이 값이 현재 덱의 front 요소의 중요도보다 크다면 front 요소를 덱의 맨 뒤로 넣어주고, 그렇지 않다면 cnt 값을 1 증가시키고 덱에서 front 요소를 빼는 식으로 구현한다.
4. 그런데 만약 내가 궁금했던 요소의 인덱스와 현재 빼려고 하는 요소의 인덱스가 같다면 cnt 값을 출력하고 while 문을 종료하도록 한다.

 

위와 같은 풀이 방식으로 코드를 구현하면 쉽게 해결할 수있는 문제였다. 다른 사람들 풀이도 봤는데 나랑 진짜 거의 똑같이 푼 사람도 있어서 재밌었다. 

 

 

 

참고자료:

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

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

-> 이게 나랑 풀이 방법이 거의 비슷한 코드였다.

 

[C언어] 백준 1966번: 프린터 큐 : 네이버 블로그

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

-> 이건 완전 다르게 풀었는데 신기해서 가져와봤다.