[BOJ] 1966 : 프린터 큐

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

1966번: 프린터 큐

 

풀이

문제를 잘 읽어보면 Priority Queue를 이용해서 문제를 풀이하면 된다. 하지만 나는 문제를 보고 Circular Queue가 생각이 났다. 배열에 나머지 연산을 이용하여 Circular Queue를 구현하고 최댓값을 갱신하여 문제를 풀었다.

Queue는 FIFO (First In First Out) 방식으로 먼저 온 데이터가 먼저 나가게 된다. 문제에서 우선순위가 밀리는 수가 나오면 다시 맨 뒤로 보내기 때문에, Circular Queue에서는 우선순위에서 밀리는 수는 그냥 건너뛰고 순서는 카운트하지 않는다. 그리고 우선순위가 가장 높은 수가 나올 경우에는, Queue에서 그 수가 pop 된 것처럼 0으로 바꾸어 주었다.

 

코드

#include <stdio.h>
 
int Max(int arr[], int n);
 
int main(void) {
  int x[101];
  int n, m, a, max;
  int cnt = 0, idx = 0, odr = 0;
 
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    scanf("%d %d", &m, &a);
    for(int j = 0; j < m; j++) {
      scanf("%d", &x[j]);
      cnt++;
    }
    max = Max(x, cnt);
    
    while(1) {
      if(x[idx%cnt] == max) {
        if(idx%cnt == a) {
          printf("%d\n", ++odr);
          break;
        }
        else {
          ++odr;
          x[idx%cnt] = 0;
          max = Max(x, cnt);
        }
      }
      idx++;
    }
    idx = 0;
    odr = 0;
    cnt = 0;
  }
 
  return 0;
}
 
int Max(int arr[], int n){
  int max = 0x80000000;
  for(int i = 0; i < n; i++){
    max = max < arr[i] ? arr[i] : max;              
  }
  return max;
}