✅ queue ✅ priority_queue

문제

링크

풀이

1. 문제 접근

2. 자료구조 선택과 그 이유

중요도가 따로 주어지며 중요도에 따라 문서의 출력순서가 달라지므로 출력순서를 알기위해 우선순위 큐를 사용해야 한다.
또한 기존에 주어진 수열을 기준으로 차례가 아닌 경우 뒤로 이동하므로 일반 큐도 필요하다.

3. 문제 해결 로직 (풀이법)

의사코드

    int T;
    cin >> T;

    while (T--)
    {
        queue<pair<int, int> > que;
        priority_queue<int> pq;

        cin >> N >> M;

        for (int i = 0; i < N; i++)
        {
            cin >> X;
            // queue는 index가 없기 때문에 pair을 이용하여 index를 같이 넣어줌
            que.push(make_pair(i, X));
            // 중요도 순으로 인쇄 순서를 알기 위해 우선순위 queue 사용
            pq.push(X);
        }

        while (!que.empty())
        {
            int index = que.front().first;
            int value = que.front().second;
            que.pop();

            if (value == pq.top()) // 중요도 순으로 인쇄할 차례일 경우
            {
                cnt++;
                pq.pop();

                if (index == M) // 찾고자 하는 순서일 경우
                {
                    cout << cnt << '\n';
                    break;
                }
            }
            else // 인쇄할 차례가 아닐 경우, 다시 que에 push
            {
                que.push(pair(index, value));
            }
        }
    }

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

우선순위 큐와 일반 큐를 같이 사용해야하는 처음 접해보는 유형의 문제