[백준 / C언어] 1966번: 프린터 큐 (배열을 이용해서 풀기)

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

1966번: 프린터 큐

 

난이도: solved.ac 실버 3

 

 

접근 방법

---

배열을 이용하면 어렵지 않게 풀 수 있다

입력받은 수들을 저장할 배열(queue)과 각 우선순위가 몇 개씩 있는지 저장할 배열(prior)을 이용한다

그리고 커서(cur)를 이용해 queue의 맨 앞 원소부터 한 칸씩 이동하며 제거할지 말지 결정한다

cur가 가리키는 문서의 우선순위가 가장 높아 제거해야 한다면 해당 문서의 우선순위 개수를 하나 감소시키고

더 높은 우선순위의 문서가 있다면 cur만 한 칸 이동시킨다

이때 더 높은 우선순위가 있는지는, 배열 prior에서 가장 높은 인덱스부터 낮은 인덱스로 내려오면서 값이 0이 아닌 원소가 있는지로 파악한다

 

아래는 예제 입력 1의 세 번째 테스트 케이스가 어떻게 진행되는지 나타낸 것이다

참고하면 이해하기 쉬울 것이다

 

구현

---

각 테스트 케이스마다 queue를 calloc으로 동적 할당해 주고, 각 원소를 입력받아서 queue에 저장할 때마다 배열 prior에는 해당 문서의 우선순위의 개수를 1씩 증가시켜 준다

(Ex. 입력받은 문서의 우선순위가 4라면, prior[4]++)

그리고 변수 max를 이용해 가장 높은 우선순위가 뭔지 알아내고 while문에서는 해당 우선순위의 문서부터 제거하도록 해준다

그리고 문서를 제거하면 queue에서 해당 값을 -1로 바꿔주고, prior에서는 해당 우선순위의 개수를 1 감소시켜 준다

원하는 문서를 제거한 뒤 한 테스트 케이스가 끝나면 다음 테스트 케이스를 위해 queue를 free 시켜주고, prior의 모든 원소를 memset을 이용해 0으로 초기화 시켜준다

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

int prior[10];	// 우선 순위

int main() {
	int T;
	scanf("%d", &T);
	while(T) {
		int N, find, max = 0;
		scanf("%d %d", &N, &find);
		int* queue = (int*)calloc(N, sizeof(int));

		int cur = -1, cnt = 0;
		for (int i = 0; i < N; i++) {
			scanf("%d", &queue[i]);
			prior[queue[i]]++;
			if (queue[i] > max)
				max = queue[i];
		}

		while (queue[find] != -1) {
			cur++;	// 커서 한 칸 이동

			// cur가 배열의 범위를 초과하면 맨 앞으로 오도록
			cur %= N;
			// cur가 가리키는 문서가 가장 중요도 높은 문서라 제거해야 할 때
			if (queue[cur] == max) {
				cnt++;
				queue[cur] = -1;
				prior[max]--;
				
				// 제거한 문서의 중요도와 같은 문서가 더이상 없을 때
				if (prior[max] == 0) {
					max--;
					while (!prior[max]) max--;
				}
			}
		}
		printf("%d\n", cnt);
		free(queue);
		memset(prior, 0, sizeof(int) * 10);
		T--;
	}
	return 0;
}