백준 1966번 [프린터 큐](C++)-yes6686- 티스토리

백준 문제 풀이: 1966 [프린터 큐]

---

문제 링크: https://www.acmicpc.net/problem/1966

문제 설명:

문서의 중요도가 주어졌을 때, 주어진 위치의 문서가 몇 번째로 출력되는지를 구하는 문제입니다. 문서의 출력 순서는 중요도가 높은 순으로 결정되며, 중요도가 같을 경우 입력된 순서를 따릅니다.

---

문제 해결 코드

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int cnt;
    int T;
    cin >> T;
    int n, m;
    int k;
    while (T--) {
        cnt = 0;
        cin >> n >> m;
        queue<pair<int, int>>q;
        priority_queue<int>pq;
        for (int j = 0; j < n; j++) {
            cin >> k;
            q.push({ j, k });
            pq.push(k);
        }
        while (!q.empty()) {
            int idx = q.front().first;
            int val = q.front().second;
            q.pop();
            if (pq.top() == val) {
                pq.pop();
                cnt++;
                if (idx == m) {
                    cout << cnt << endl;
                    break;
                }
            } else {
                q.push({ idx, val });
            }
        }
    }
}

---

코드 설명

• 입력: 테스트 케이스 수(T), 문서의 개수(n), 타겟 문서의 인덱스(m), 그리고 각 문서의 중요도.
• 로직:
  • 각 문서를 queue에 삽입하며, 중요도를 priority_queue에 삽입하여 정렬된 상태로 유지합니다.
  • 큐에서 문서를 하나씩 꺼내며, 현재 문서의 중요도가 priority_queue의 최상위 값과 같은지 확인합니다.
  • 중요도가 같으면 출력 순서를 증가시키고, 그렇지 않으면 큐의 뒤로 다시 삽입합니다.
  • 타겟 문서가 출력된 경우 해당 순서를 출력합니다.
• 출력: 각 테스트 케이스별로 타겟 문서가 출력되는 순서를 출력합니다.

시간 복잡도

각 문서에 대해 큐와 우선순위 큐 연산을 수행하므로 시간 복잡도는 O(T * n log n), 여기서 T는 테스트 케이스의 수, n은 문서의 개수입니다.

---

결과

이 코드는 주어진 문서 순서를 정확히 계산합니다. 큐와 우선순위 큐를 활용하여 중요도와 순서를 동시에 관리하는 점이 효율적입니다. 더 나은 접근 방법이나 개선 사항이 있다면 자유롭게 공유해주세요!