[BOJ] 프린터 큐_1966.c++

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음줄에 N개 문서의 중요도가 주어지는데, 중요도는 1 이상 9 이하이다. 중요도가 같은 문서가 여러 개 있을 수도 있다. 위의 예는 N=4, M=0(A문서가 궁금하다면), 중요도는 2 1 4 3이 된다.

출력

각 test case에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void printer_queue(){
    vector<pair<int, int>> doc;
    vector<pair<int, int>> sorted;
    vector<pair<int, int>> temp;
 
    int N, M, priority, count = 0;
    cin >> N >> M;
    for (int i = 0; i < N; i++){
        cin >> priority;
        doc.push_back(make_pair(priority, i));
    }
    sorted = doc;
    sort(sorted.begin(), sorted.end(), greater<>());
 
    while(1){
        for(int i = 0; i != doc.size(); i++){
            if((doc[0].second == M) && (doc[0].first == sorted[count].first)){cout << count+1 << endl; return;}
            else if(sorted[count].first == doc[0].first){
                count++;
                doc.erase(doc.begin());
                break;
            }
            else{
                temp.push_back(doc[0]);
                doc.erase(doc.begin());
                doc.push_back(temp.front());
                temp.clear();
            }
        }
    }
}
 
int main(){
    int test_case;
    cin >> test_case;
    for (int i = 0; i < test_case; i++) { printer_queue(); }
    return 0;
}
 

3시간 넘게 고민해서 풀었다..

이 문제의 알고리즘 분류에는 '큐' 가 있다. 그래서 큐 를 써서 문제를 풀려니까 자꾸 나사가 하나 빠진 느낌이 들었다.

stl container queue에는 vector의 at 이나 begin, [] 처럼 원하는 위치의 값을 알 수가 없다.

그래서 그냥 vector를 썼다. stl algorithm 의 sort를 쓰고 vector에 pair를 붙여주니까 핵심코드가 꽤 간단하게 나온것같다!

사실 고민 시간의 대부분이 sort algorithm사용법, pair사용법, queue에 포함된 함수를 알아보느라고 오래걸렸다.

그 덕분에 c++과 더 친해지게 되었다

 

 

Queue

#include <queue>

using namespace std;

queue<typename T> que1;

queue<pair<int, int>> que2;

 

#include <vector>

#include <algorithm>

using namespace std;

vector<typename T> vec1;

vector<pair<int, int>> vec2;

 

//vector변수에 pair 형으로 값을 넣는법

vec2.push_back(make_pair(4,5));

vec2.push_back(pair<int, int>(3, 6));

 

//algorithm   sort함수 사용하기

sort(vec2.begin(), vec2.end(). less<>());         //오름차순 정렬

sort(vec2.begin(), vec2.end(). greater<>());    //내림차순 정렬

 

bool cmp(const typename T a, const typename T b){

    if(a.first == b.first){    //pair의 첫 번째 원소가 같으면

        return a.second > b.second;    // 두 번째 원소값에 따라 내림차순

    }

    else{

        return a.first < b.first;    //pair의 첫 번째 원소가 다르면 첫 번째 원소값에 따라 오름차순(일반적인 sort())

    }

}

 

c++을 제대로 공부한지 10일쯤 된거같다

알면 알수록 c++은 c언어에 비해서 훨씬 편하고 기능도 많아서 좋다

 

개강 시러