[BOJ알고리즘, C++]#1966_프린터 큐, 우선순위 큐, 큐

 

[BOJ알고리즘, C++]#1966_프린터 큐

 

BOJ 알고리즘 문제 풀이, 1966번 문제 프린터 큐

queue컨테이너와 priority_queue 컨테이너를 활용하는 방법에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#0. 문제

 

 

#1. 풀이

1. 큐

[자료 구조]#0_선형 자료구조

 

• 큐는 먼저 들어온 데이터가 먼저 처리되는 FIFO(First In First Out) 방식으로 동작하는 선형 자료구조입니다.
• 데이터 목록의 한쪽에서만(top) 접근이 가능한 스택과 달리, 큐는 데이터 목록의 양쪽 끝(front, back)에서 접근이 가능합니다.
• 삽입/제거의 위치와 방법이 제한된 유한 순차 리스트라는 점에서 스택과 동일하지만, 큐는 스택과 달리 push 한 데이터와 pop 한 데이터가 다릅니다!
• 큐는 그래프 자료구조의 BFS(너비 우선 탐색)에 활용되며, 작업들을 순차적으로 처리하거나, 멀티 스레드 환경에서 동기화를 위한 버퍼로 활용됩니다.

 

2. queue 컨테이너

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;

    // 큐에 데이터 삽입
    q.push(1);
    q.push(2);
    q.push(3);

    // 큐의 맨 앞 데이터 제거
    q.pop();

    // 큐의 맨 앞 데이터 출력
    cout << "Front element of the queue: " << q.front() << endl;

    // 큐의 맨 뒤 데이터 출력
    cout << "Back element of the queue: " << q.back() << endl;

    // 큐의 크기 출력
    cout << "Size of the queue: " << q.size() << endl;

    return 0;
}

 

Details

 

1. C++의 STL이 제공하는 queue 컨테이너의 삽입 방법은 push입니다.
2. C++의 STL이 제공하는 queue 컨테이너의 제거 방법은 pop입니다.
3. C++의 STL이 제공하는 queue 컨테이너의 접근 방법은 front(), 그리고 back()입니다.

 

3. 우선순위 큐

[자료구조]#7_우선순위 큐

 

• 우선순위 큐는 각 원소에 우선순위를 할당하여, 가장 높은 우선순위를 갖는 원소가 다른 원소보다 먼저 처리되는 자료구조입니다.
• 우선순위 큐는 가장 높은 우선순위를 갖는 원소가 맨 앞에 위치하며, 우선순위 큐의 삭제작업은 우선순위가 가장 높은 원소의 삭제를 의미합니다.
• 우선순위 큐의 우선순위는 일반적으로 비교 연산자를 사용하여 지정합니다. 
• 우선순위 큐의 접근 연산은 O(1)의 시간 복잡도를 가지며, 삽입/삭제 연산의 시간 복잡도는 O(log n)입니다.

 

4. priority_queue 컨테이너

[Basic C++] #69_priority_queue

 

5. 우선순위 큐 활용 

• 먼저, 큐를 활용해 pair <int, int> 유형의 값을 저장합니다. 이때, pair의 first는 문서의 Index를 의미하고, second는 문서의 중요도 값을 의미합니다.
• 다음으로, 우선순위 큐에 중요도 값을 삽입합니다. 우선순위 큐의 디폴트 정렬 기준은 내림차순입니다. 따라서, 중요도 값이 높을수록 우선순위가 높아집니다.
• 큐에 대해 반복문을 수행하고, 큐의 맨 앞에 위치한 값이 우선순위 큐의 맨 앞에 위치한 값과 일치할 경우 큐와 우선순위 큐 모두 pop()을 수행하고, 그렇지 않다면 큐의 맨 앞에 위치한 값을 큐의 마지막 위치로 옮기는 작업을 반복합니다.

 

#2. 코드

1. 코드

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

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

    int T, N, M, tmp;
    queue<pair<int, int>> q;
    priority_queue<int> pq;

    cin >> T;

    while(T--)
    {
        cin >> N >> M;
        for(int i=0; i<N; i++)
        {
            cin >> tmp;
            q.push({i, tmp});
            pq.push(tmp);
        }
        int ans = 0;
        while(!q.empty())
        {
            int Idx = q.front().first;
            int Imp = q.front().second;
            q.pop();
            if(Imp == pq.top())
            {
                pq.pop();
                ans++;
                if(Idx == M)
                {
                    cout << ans << '\n';
                }
            }
            else
            {
                q.push({Idx, Imp});
            }
        }
    }

}