백준 - 프린터 큐(C++)

구현코드

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

[

1966번: 프린터 큐

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에

www.acmicpc.net

](https://www.acmicpc.net/problem/1966)

문제설명

1. 제목 그대로 큐를 사용하면 된다. 자료구조을 이용하는 문제임을 쉽게 알 수 있다.

알고리즘

1. queue 와 중요도가 높은 문서를 알 수 있는 어떠한 가이드가 필요하다.

2. 가이드를 vector를 이용했다. vector를 정렬하여 높은 숫자가 빠지면 vector의 index도 증가하도록 하였다.

주의사항

1. PQ를 이용하는 알고리즘도 생각했는데, PQ 1개로 구현 할 수 있는 방법이 없는 것 같아서 이 방법을 사용했다.

구현

struct Cmp
{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        if (a.first == b.first)
            return a.second > b.second;
        return a.first < b.first;
    }

};

bool cmp(int a, int b)
{
    return a > b;
}


int main() {
    scanf("%d", &T);
    // queue에는 중요도와 자기 번호
    //pq로 하면 안됨고유 순서가 무너짐
    for (int i = 0; i < T; i++)
    {
        int N = 0, pos = 0;
        queue<pair<int, int>> q;
        vector<int> v;
        scanf("%d %d", &N, &pos);

        for (int j = 0; j < N; j++)
        {
            int a = 0;
            scanf("%d", &a);
            v.push_back(a);
            q.push({ a,j }); // 중요도 , 순서
        }
        sort(v.begin(), v.end(), cmp);
        int idx = 0, cnt = 1;
        while (true)
        {
            int imp = q.front().first;
            int ord = q.front().second;
            q.pop();

            if (imp >= v[idx])
            {
                idx++;
                if(ord == pos)
                    break;
            }
            else
            {
                q.push({ imp,ord });
            }
        }
        printf("%d\n", idx);
    }
}