[알고리즘/문제풀이/BOJ 1966번] 프린터 큐

프린터 큐는 큐를 활용해서 푸는 문제이다. 다만 단순히 큐만을 사용하는 문제는 아니었다. 큐에 있는 원소의 우선순위 중 가장 높은 수를 알아야 하는 데 이때 구글링을 해보면 우선순위 큐를 사용하는 유저들이 많았다. 아직 우선순위 큐에 대해 다루지 않았기 때문에 이번 풀이에서는 계수를 이용해서 문제를 풀었다. 해당 우선순위를 가지는 값의 개수를 저장하는 배열을 선언하고, 이 배열을 조사함으로써 현재 큐에서 우선순위가 가장 큰 경우를 찾고 그 값에 따라 큐에서 pop을 한 값을 다시 push할지 하지 않을 지 결정하는 식으로 해결하였다.

관찰한 값을 표시하기 위해 flag 변수가 필요했고, 구조체를 활용하여 flag와 우선순위 값을 묶고, 구조체를 원소로 하는 배열을 선언하였다. 다른 풀이에서는 구조체가 아닌 2차원 배열을 선언하여 flag와 우선순위 값을 함께 저장해서 더욱 빠른 속도를 얻을 수 있었던 것 같다.

아무튼 우선순위 큐 없이 프린터 큐를 해결할 수 있었다.

작성한 코드는 다음과 같다.

---

#include<stdio.h>

int T;
int N, M;
int temp;
int cnt;
int max;

int count[10];

typedef struct element {
int prior;
char check;
} ELEMENT;

ELEMENT queue[120];

int head, tail;

void pop() {
head += 1;
head %= 120;
}

void push(int num, int check) {
queue[tail].prior = num;
queue[tail].check = check;
tail = (tail + 1) % 120;
return;
}


int main(void) {
scanf("%d", &T);

for (int i = 0; i < T; i++) {
scanf("%d %d", &N, &M);
head = 0;
tail = 0;
cnt = 0;
for (int i = 0; i < 10; i++)
count[i] = 0;

for (int i = 0; i < N; i++) {
scanf("%d", &temp);
count[temp]++;
push(temp,0);
}
queue[M].check = 1;

for (int i = 9; i >0; i--) {
if (count[i] > 0) {
max = i;
break;
}
}

while (1) {

if (queue[head].prior < max) {
push(queue[head].prior, queue[head].check);
pop();
}
else if(queue[head].prior == max){
if (queue[head].check == 1) {
cnt++;
break;
}
else {
pop();
count[max]--;
while (count[max] == 0) {
max--;
}
cnt++;
}

}
}

printf("%d\n", cnt);

}
}