백준 1966 프린터 큐 / C++

문제 : 1966

풀이 point

큐에서의 순서와 중요도가 매우 중요하다

N이 100이라 굉장히 작으므로 $N^2$을 봐도 된다.
(T의 범위가 주어지지 않아 정확하지 않을 수 있음)

큐의 맨앞 문서의 중요도가 뒤에 있는 문서들의 중요도 보다 하나라도 낮을 경우 뒤로 보낸다. 만약 맨앞 문서가 내가 알고 싶은 문서였다면 출력하고 종료한다.
이렇게 내가 원하는 문서가 나올때까지 계속해서 돌려보면 된다.

풀이 방법

큐를 통해 중요도와 문서의 순서를 저장하여 알고리즘을 짰다.
우선순위 큐로도 해결가능하다.

코드

//백준 1966, 프린터 큐
#include <iostream>
#include <deque>

int main(){

    int t;
    std::cin >>t;
    while(t--){
        int N, M;
        std::cin >> N >> M;
        std::deque<std::pair<int, int>> note; //중요도, 순서

        for(int i{0}; i<N; ++i){
            int n; std::cin >> n;
            note.push_back({n, i});
        }

        int order{0};
        
        while(!note.empty()){
            bool flag = false;
            for(int i{0}; i<note.size(); ++i){
                if(note.front().first < note[i].first){
                    flag = true;
                    break;
                }
            }
            
            if(flag){
                auto tmp = note.front();
                note.pop_front();
                note.push_back(tmp);
            }
            else{
                ++order;
                if(note.front().second == M){
                    std::cout << order << '\n';
                    break;
                }
                note.pop_front();
            }
        }
    }

    return 0;
}