[C++] 백준 - 1966 : 프린터 큐

문제 링크

1966번: 프린터 큐

 

풀이 ) 큐

  stl 큐와 페어를 사용했다.

  중요도와 입력된 순서를 쌍을 이루는 페어 큐를 생성한 후 중요도를 확인하기 위한 배열을 만들었다.

  문제의 조건에 따라 큐에서 pop을 한 후 pop한 페어의 first를 확인하고 확인하기 위한 배열의 요소와 비교하여 중요도가 더 큰 문서가 있으면 다시 push를 해준다.

  중요도가 더 큰 문서가 없는 경우 출력하고 이 때 출력된 문서가 문제에서 요구하는 문서( m번째 )가 맞다면 결과( cnt )를 출력한다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

int main(void)
{
  int c;
  scanf("%d", &c);
  while(c--){
    queue<pair<int, int>> q;
    pair<int, int> intp;
    int n, m, tmp, p[10];
    fill(p, p+10, 0);

    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i){
      scanf("%d", &tmp);
      p[tmp]++;
      intp = make_pair(tmp, i);
      q.push(intp);
    }
    int cnt = 1;
    while(1){
      intp = q.front();
      tmp = intp.first;
      q.pop();
      p[tmp]--;
      int flag = 0;
      for(int i = 9; i > tmp; --i){
        if(p[i]){
          flag++;
          break;
        }
      }
      if(flag){
        q.push(intp);
        p[tmp]++;
      }
      else{
        if(intp.second == m)
          break;
        cnt++;
      }
    }
    printf("%d\n", cnt);
  }
  return 0;
}