[백준 1966] 프린터 큐

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

1966번: 프린터 큐

 

약한 유형이어서 정리해본다.

 

문제의 핵심: 큐가 2개 필요하다.

1) 순서를 저장하기 위해 필요한 큐 2) 주어진 값들 중 최댓값을 찾기 위한 우선순위 큐

 

문제의 조건에서 선택되지 못한 숫자는 맨 마지막 열에 다시 합류하므로 이 순서를 저장할 큐가 필요하며

주어진 숫자 중 최댓값을 매번 찾아야 하므로 우선순위 큐가 필요하다.

 

접근법:

큐에는 인덱스와 값을

우선순위 큐에는 값만 저장한다.

 

1. IF 우선순위 큐의 가장 앞에 있는 (최댓값) 값 == 큐의 가장 앞에 있는 값 

1-1. 그 인덱스가 찾고자 하는 M일 경우 리턴

1-2. M은 아니라면 우선순위큐와 큐 모두 팝

 

2.  IF 우선순위 큐의 가장 앞에 있는 (최댓값) 값 != 큐의 가장 앞에 있는 값 

2-1. 다른 값을 찾아야 하므로 큐의 탑을 POP & 뒤로 PUSH한다.

 

#include <queue>
#include <stdio.h>

using namespace std;

int t, n, m;
int main(void)
{
  scanf("%d", &t);
  while (t--)
  {
    scanf("%d%d", &n, &m);
    priority_queue<int> pq;
    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++)
    {
      int val;
      scanf("%d", &val);
      pq.push(val);
      q.push({i, val});
    }

    int cnt = 1;
    while (!pq.empty())
    {
      int mval = pq.top();
      int fval = q.front().second;
      int fidx = q.front().first;
      q.pop();
      if (mval == fval) // 가장 앞에 위치한 값이 최댓값이라면
      {
        // 찾는 위치의 값이면 종료
        if (fidx == m)
        {
          printf("%d\n", cnt);
          break;
        }
        pq.pop();
        cnt++;
      }
      else
      {
        q.push({fidx, fval});
      }
    }
  }
  return 0;
}