[백준] 1966번 프린터 큐

 

 

문제

소스코드

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
using Element=std::pair<int, bool>;
 
int ProcessQueue(std::deque<Element>&& printerQueue) {
 
    int count{};
 
    while (printerQueue.empty() == false) {
        auto frontValue = printerQueue.front();
        auto maxValue = *std::max_element(printerQueue.begin(), printerQueue.end());
 
        printerQueue.pop_front();
 
        //앞에있는게 가장 우선순위가 높다면 
        if (frontValue.first >= maxValue.first) {
            ++count;
 
            if (frontValue.second == true) {
                return count;
            }
        }
        //우선순위가 더 높은게 queue안에 있다면
        else {
            printerQueue.emplace_back(frontValue);
        }
    }
}
 
 
int main() {
    //Test case
    int N{}, queueSize{}, M{};
    std::vector<int> answerVector{};
 
    std::cin >> N;
 
    for (int i = 0; i < N; ++i) {
        std::deque<Element> printerQueue;
        std::cin >> queueSize >> M;
 
        for (int i = 0; i < queueSize; ++i) {
            int value{};
            std::cin >> value;
            if (i == M) {
                printerQueue.emplace_back(Element(std::move(value), true));
            }
            else {
                printerQueue.emplace_back(Element(std::move(value), false));
            }
        }
        answerVector.emplace_back(ProcessQueue(std::move(printerQueue)));
    }
    //Print answer
    for (const auto& answer : answerVector) {
        std::cout << answer << "\n";
    }
}

 

후기

이 문제를 해결하기 위한 키워드는 Deque이다.

 

Deque은 STL 컨테이너 중 하나로 배열의 앞과 끝에서 삽입과 삭제가 자유로운 자료구조이다.

이 자료구조를 이용하면 우선순위가 더 낮은 원소를 뒤에 보내기 용이하며 std::max_element(가장 큰 원소를 찾는 알고리즘)을 사용하기 편하기 때문에 사용했다.

 

Deque의 원소에는 std::pair <int.bool>을 사용했으며 첫 번째 원소는 숫자 값을 두 번째 원소는 내가 찾고자 하는 원소인지를 구별하는 true/false이다. 이렇게 원소에 bool 값을 추가하면 중복된 숫자가 있을 경우에 찾기가 용이하다.

 

 

 

 

출처 및 레퍼런스

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