[Silver 3] 1966번 프린터 큐

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

이 문제는 큐를 사용하였다.

이때, 배열에 우선순위를 넣고, 입력이 끝나면 정렬하여 앞에서부터 꺼내 사용했다.

큐에 넣을 요소는 구조체를 생성하여 우선 순위와 입력 순서를 저장할 수 있도록 하였다.

 

알고리즘으로는 큐의 앞에서부터 꺼내되, 요소의 우선순위가 배열에서 꺼낸 max 값보다 낮으면 다시 삽입하고

max값에 해당하면 max 값을 그 다음 순위로 갱신하고, 배열의 범위를 벗어나지 않는 조건하에 반복을 이어 갔다.

반복문의 조건으로는 원하는 입력 순서를 찾게되면 멈추게 하였다.

 

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

typedef struct Element {
    int priority;
    int value;
} Element;

bool bigger(int a, int b) {
    if (a > b) return true;
    else return false;
}

int main() {
    int T;
    cin >> T;

    for (int i = 0; i < T; i++) {
        queue<Element> q;
        vector<int> p;
        int N, M;
        cin >> N >> M;
        for (int j = 0; j < N; j++) {
            int input;
            cin >> input;
            Element e;
            e.priority = input;
            e.value = j;
            q.push(e);
            p.push_back(input);
        }
        sort(p.begin(), p.end(), bigger);
        
        int maxIndex = 0;

        int max = p[maxIndex];
        int find = -1;
        int count = 0;
        while (M != find) {
            Element e = q.front();
            q.pop();
            if (e.priority < max) {
                q.push(e);
            }
            else {
                count += 1;
                find = e.value;
                maxIndex += 1;
                if (maxIndex < p.size())
                    max = p[maxIndex];
                else
                    break;
            }
        }
        cout << count << '\n';

    }
}