[백준] 1966. 프린터 큐
: solved.ac class 2 - silver 3
https://www.acmicpc.net/problem/1966
예제 입력
3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1
예제 출력
1
2
5
정답
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int queue[100];
int printQ(int n, int m)
{
int cnt = 1;
int front = 0;
int max = 0;
while (1) {
for (int j = 0; j < n; j++) {
if (queue[j] > max) max = queue[j];
}
while (queue[front] != max) {
front = (front + 1) % n;
}
if (front == m) break;
queue[front] = 0;
front = (front + 1) % n;
max = 0;
cnt++;
}
return cnt;
}
int main() {
int t;
int n, m;
scanf("%d", &t);
for (int i = 0; i < t; i++) {
scanf("%d %d", &n, &m);
for (int j = 0; j < n; j++) {
scanf("%d", &queue[j]);
}
printf("%d\n", printQ(n, m));
}
return 0;
}
해설
- 원형 큐를 이용한다.
- 우선순위 배열을 순회하며 가장 높은 우선순위를 가진 원소를 찾고 -> 초기화하는 것을 반복한다. 이때마다 해당 원소를 '인쇄'한 것으로 간주하여 누적 순번 변수(cnt)를 하나씩 증가시킨다.
- 대상 원소(m번째 원소)가 해당 배열에서 가장 높은 우선순위를 갖게 되어 인쇄의 대상이 되면 해당 시점의 누적 순번 변수를 print한다.
- (자세한 구현 아이디어는 하단 이미지 참고)
1. 필요한 변수들과 배열을 선언해 준다. 프린트 큐에는 최대 100개의 원소가 들어오게 되어 있으므로 배열 크기도 그에 맞춘다. 첫 줄에는 테스트 케이스의 개수를, 두번째 줄부터는 n, m과 배열을 두 줄 단위로 받아준다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int queue[100];
int main() {
int t;
int n, m;
scanf("%d", &t); //테스트 케이스의 개수 t
for (int i = 0; i < t; i++) { //테스트 케이스 개수만큼 반복
scanf("%d %d", &n, &m);
//문서의 개수 n과 대상 문서의 초기 순번 m 입력받기
for (int j = 0; j < n; j++) {
scanf("%d", &queue[j]);
} //우선순위 배열 입력받기
printf("%d\n", printQ(n, m));
//별도 함수로 구한 결과값 출력
}
return 0;
}
2. 해당 테스트케이스의 n과 m을 받아 대상 문서의 출력 순번을 반환하는 함수이다.
문제에서는 '우선순위가 낮은 프린트는 큐의 맨 뒤로 이동한다'라고 묘사되어 있으나 그러한 구조를 그대로 구현한다면 (실제 입력받은 배열 뒤에 원소를 덧붙이는 등) 공간의 확장이 필요하며, 시간적인 문제 또한 따라올 수 있다. 하여 생각할 수 있는 방법이 원형 큐 구조를 이용하는 것이다. 정확히는, 나머지 연산(%)을 사용한 식을 활용한다.
다시 말하자면 변수가 배열의 인덱스를 한 칸씩 순차적으로 가리키도록 하되, 배열의 끝에 다다르면 다시 배열의 시작점으로 돌아오도록 하는 것이다. 이 순회 동작은 front = (front+1)%n이라는 문장으로 구현된다.
위와 같은 방법을 사용하면 원소가 큐의 맨 뒤로 이동하는 것과 같은 효과를 얻을 수 있다. 큐의 뒤로 원소가 이동하는 것도 결국은 선입선출의 특징을 가지기 때문에 굳이 실제로 원소가 이동할 필요가 없는 것이다. 필요한 출력값은 '해당 원소가 몇 번째로 인쇄되는지'에 대한 값이므로, 순회를 반복하여 인쇄되는 원소를 골라내고 누적 인쇄 횟수를 증가시켜 주기만 하면 된다. 해당 원소가 인쇄 대상이 된다면 (front (== max) == m) 순회는 자연히 끝나며, 누적 인쇄 횟수가 함수의 결과값으로 반환될 것이다.
int printQ(int n, int m)
{
int cnt = 1;
int front = 0;
int max = 0;
while (1) {
for (int j = 0; j < n; j++) {
if (queue[j] > max) max = queue[j];
} //최댓값 찾기
while (queue[front] != max) {
front = (front + 1) % n;
} //최댓값 찾을 때까지 front 이동
if (front == m) break;
//대상을 프린트할 차례가 되면 반복문 탈출
queue[front] = 0; //해당 원소 우선순위 0으로 조정
front = (front + 1) % n; //front 한칸 전진 (원형 큐)
max = 0; //최댓값 초기화
cnt++; //출력한 프린트 수 1 증가
}
return cnt; //대상의 순번 출력
}