[C++] 백준 1966번: 프린터 큐 (구현)

1966번: 프린터 큐

---

문제 이해하기

  이 문제를 요약해보면 다음과 같습니다.

정해진 규칙에 따라 인쇄하는 인쇄기에서 특정 문서가 몇 번째로 인쇄되는지 구하여라.

 

  여기서 정해진 규칙이란

1. 입력은 queue 자료구조에 따른다.
2. 출력은 기본적으로 queue 자료구조에 따라 가장 앞에 있는 문서를 내보낸다.
 2-1. 만약 가장 앞에 있는 문서보다 중요도가 높은 문서가 queue 내에 존재한다면, 가장 앞의 문서를 가장 마지막으로 옮긴다.

라고 할 수 있습니다.

---

시간복잡도 어림하기

 이 문제는 정해진 규칙에 따라 코드를 구현하는 문제이므로 이 단계는 넘어가도록 하겠습니다.

---

알고리즘 설계하기

 이 문제에서 가장 핵심은 "큐에서 가장 앞에 있는 문서가 가장 중요도가 높은 원소인가?"를 판단하는 것입니다. 만약, 이 조건이 참이라면 그대로 큐를 pop하면 되고, 그렇지 않다면 가장 뒤로 push하면 되니까요.

 

 그렇다면, 가장 앞에 있는 문서가 가장 중요도가 높은지는 어떻게 판별할 수 있을까요?

 가장 단순하게 생각해보면, 모든 문서의 우선도를 담은 배열이나 벡터를 정렬하여 맨 앞에 있는 문서의 중요도와 비교하면 되지 않을까요? 또 다른 방법으로 우선도가 가장 높은 문서가 큐에 가장 앞에 오는 우선순위 큐도 가능할 것 같습니다.

 

 벡터를 사용하는 방식에서는 정렬 함수인 sort를 사용하면 O(nlogn)의 시간 만에 정렬을 끝낼 수 있고, n의 최댓값이 100이므로 100log100 < 1000, 따라서 1000도 안되는 시간복잡도 안에 최댓값을 얻을 수 있습니다.

 

 우선순위 큐를 사용하는 방식에서는 우선순위 큐의 특성상 삽입과 추출의 시간복잡도가 O(logn)이므로 적은 시간복잡도로 최댓값을 얻을 수 있습니다. 따라서 두 방식 모두 문제를 해결하기 적절한 방식입니다.

 

 대략적인 방향을 정했다면, 코드의 흐름을 구상해봅시다. 제가 구상한 코드 흐름은 다음과 같습니다.

 1. 입력 받기
 2. 큐가 빌 때까지 또는 목표 문서가 출력될 때까지 아래 동작을 반복하기
  2-1. 큐의 가장 앞에 있는 문서를 꺼내 중요도의 최댓값과 비교하기
   2-1-1. 현재 문서의 중요도가 남은 문서의 중요도의 최댓값보다 작다면, 현재 문서를 큐에 push
   2-1-2. 그렇지 않다면 중요도의 최댓값을 제거하고, 순서를 카운트한다.

 

 이제, 위 코드 흐름을 기반으로 벡터를 사용한 방식과, 우선순위 큐를 사용한 방식 모두 보여드리겠습니다.

---

알고리즘 구현하기

 벡터 사용

#include<iostream>
#include<queue>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;

int t, n, m, num;
int main(){
	/*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> t;
    while(t--){
        queue<pair<int, int>> q;
        vector<int> v;
        cin >> n >> m; //n은 문서의 수, m은 출력 순서를 확인할 문서의 위치
        for(int i = 0; i < n; i++){
            cin >> num;
            q.push({num, i});
            v.push_back(num);
        }
        sort(v.begin(), v.end(), greater<int>());
        
        int x, y, idx = 0;
        while(q.size()){
            tie(x, y) = q.front(); q.pop();
            if(x < v[0]) q.push({x, y});
            else{
                v.erase(v.begin());
                idx++;
                if(y == m){ cout << idx << '\n'; break; }
            }
        }
    }
    return 0;
}

 main 함수의 첫 두 줄은 cin의 성능을 높이기 위한 코드입니다. 자세한 내용은 cin 성능 향상에 대해 검색해보시길 바랍니다.

 

 테스트 케이스 루프에서는 큐와 벡터를 선언해주었습니다. 전역 변수로 선언하지 않고 지역 변수로 선언한 이유는 매 테스트케이스마다 큐와 벡터를 초기화 해야하기 때문입니다. 만약, 전역 변수로 사용하길 원한다면 반드시 초기화 함수를 사용하여 큐와 벡터를 초기화 해야합니다.

 

 큐에 저장할 타입은 pair<int, int>로 첫 번째 원소는 문서의 중요도, 두 번째 원소는 처음 프린터 큐에 들어있는 문서의 위치 입니다.

 

 입력을 모두 받을 후 벡터를 정렬하여 중요도가 가장 높은 값이 가장 앞으로 오도록 정렬합니다. 즉, 내림차순으로 정렬합니다. <algorithm> 헤더 파일의 sort 함수는 기본적으로 오름차순으로 정렬하기 때문에, 마지막 인자에 greater<int>()을 넣어 내림차순으로 정렬되도록 합니다.

 

 다음으로는 목표 문서의 출력 순서를 찾습니다.

 먼저 큐의 가장 앞 원소를 꺼내고, 큐에서 pop합니다. 이때, <tuple> 헤더파일의 tie함수를 사용하면 x, y에 각각 값을 대입해 주지 않아도 자동으로 pair<int, int> 값을 대입해줍니다.

 

 이후 중요도를 비교한 뒤, 현재 문서의 중요도가 남은 문서의 중요도의 최댓값이 아니라면 그대로 큐에 push하고, 그렇지 않다면 최댓값을 제거하여 순서를 카운트합니다.

 이 과정을 목표 문서를 찾을 때까지 반복하면 문제를 해결할 수 있습니다.

우선순위 큐 사용

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

int t, n, m, num;
int main(){
	/*입출력 성능 향상*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> t;
    while(t--){
        priority_queue<int> pq;
        queue<pair<int, int>> q;
        cin >> n >> m; //n은 문서의 수, m은 출력 순서를 확인할 문서의 위치
        for(int i = 0; i < n; i++){
            cin >> num;
            q.push({num, i});
            pq.push(num);
        }
        int x, y, idx = 0;
        while(pq.size()){
            tie(x, y) = q.front(); q.pop();
            if(x < pq.top()) q.push({x, y});
            else{
                pq.pop();
                idx++;
                if(y == m){ cout << idx << '\n'; break; }
            }
        }
    }
    return 0;
}

 우선순위 큐 사용 역시 벡터 사용과 코드가 거의 유사합니다.

 차이점이 있다면, 우선순위 큐는 디폴트가 가장 큰 값이 큐의 앞에 오기 때문에, 비교 함수를 따로 넣지 않아도 됩니다. 나머지 로직은 벡터를 사용한 코드와 동일하니 설명은 넘어가도록 하겠습니다.

---