[BOJ/백준] 1966번: 프린터 큐 (c++)

1966 문제 링크

Problem

Solution

해당 문제는 구현, 큐를 통해 해결해나간다.

1. 현재 선택된 문서가 가장 높은 중요도가 아니라면 맨 뒤로 순위가 밀려난다.

2. 중요도가 가장 높은게 선택됐다면 현재 문서를 인쇄한다.

3. 중요도가 같은 것이 있다면 그 순서대로 인쇄한다.

source code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
typedef pair<int, int> pi;

int printerQueue(int m, vector<int> num, queue<pi> printer){
    int i=0, cnt =0;
    while(!printer.empty()){
        if(printer.front().second<num[i]){
            int one = printer.front().first;
            int two = printer.front().second;
            printer.pop();
            printer.push({one,two});
        } else if(printer.front().second >= num[i++]){
            cnt++;
            if(m == printer.front().first){
                return cnt;
            }
            printer.pop();
        }
    }

    return cnt;
}

int main(){
    int t;
    int n, m;
    cin>>t;
    while(t--){
        cin>>n>>m;
        vector<int> num;
        queue<pi> printer;

        for(int i=0; i<n; i++){
            int input;
            cin>>input;
            num.push_back(input);
            printer.push({i, input});
        }
        sort(num.begin(), num.end(), greater<>());
        cout<<printerQueue(m, num, printer)<<'\n';
    }
    return 0;
}

main 함수

1. 입력받을 때 큐에 <현재 index, 중요도>를 pair로 push한다
   또 배열에도 현재 중요도를 입력한다. (이는 중요도 순서대로 출력하기 위함이다.)
2. 배열을 sort함수를 통해 내림차순 정렬한다.

printerQueue 함수

1. 큐가 비어있을 때까지 현재 큐에 들어있는 것을 확인하며 아까 저장한 배열에 있는 중요도와 같은 경우에만 인쇄한다.

2. 만약 현재 파일이 중요도가 더 낮으면 큐에 있는 것을 pop해서 다시 push 한다. (FIFO를 이용)

3. 만약 현재 파일이 중요도배열보다 값이 크거나 같다면 cnt를 증가시켜서 현재 몇번째에 출력됐는지를 표시한다.

4. 이때 입력받은 m-index와 같다면 현재 cnt를 return 한다.