[백준 1966] 프린터 큐

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

1966번: 프린터 큐

// 방법 1. 우선순위 정렬로 푸는 방법
// 우선순위 종류가 많을 때 적합하다. 
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
int T;
int N, M;
int D[100 + 10];

std::queue<int> idx;
std::queue<int> docs;

void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%d", &D[i]);
	}
}


bool compare(int a, int b)
{
	return a > b;		// 내림차순 정렬
}

int print_que(void)
{
	// 1. 초기 큐 생성
	idx = {}; docs = {};
	for (int i = 0; i < N; i++) {
		idx.push(i);
		docs.push(D[i]);
		//printf("%d %d \n", idx.back(), docs.back());
	}

	// 2. 우선순위 정렬
	std::sort(D, D + N, compare);

	// 3. 구현
	int cnt = 0;
	for (int i = 0; i < N; ) {
		int tmp_d = docs.front();
		int tmp_i = idx.front();
		docs.pop();
		idx.pop();
		if (tmp_d == D[i]) {
			cnt++;
			if (tmp_i == M) return cnt;
			i++;
		}
		else {
			docs.push(tmp_d);
			idx.push(tmp_i);
		}
	}
}

int main()
{
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		input();
		int ans = print_que();
		printf("%d\n", ans);
	}
	return 0;
}

// 방법 2. 룩업테이블로 푸는 방법
// 우선순위 종류가 적을때 적합하다. 
#include <cstdio>
#include <iostream>
#include <queue>
int T; 
int N, M;
int D[100 + 10];

int lookup[9 + 2];
std::queue<int> idx;
std::queue<int> docs;


void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%d", &D[i]);
	}
}

void init(void)
{
	for (int i = 1; i <= 9; i++) {	// 우선순위는 1부터 9까지 !
		lookup[i] = 0;
	}
}


int print_queue(void)
{
	// 1. 큐 초기화
	idx = {}; docs = {}; init();
	for (int i = 0; i < N; i++) {
		idx.push(i);
		docs.push(D[i]);
		lookup[D[i]]++;
	}
	
	// 2. 룩업테이블로 우선순위 확인
	int cnt = 0;
	for (int i = 9; i >= 1; i--) {	// 우선순위가 가장 큰 것 부터 차례대로 본다
		while (lookup[i] != 0) {
			int tmp_d = docs.front();
			int tmp_i = idx.front();
			docs.pop(); idx.pop();
			if (tmp_d == i) {
				lookup[i]--;
				cnt++;
				if (tmp_i == M) return cnt;
			}
			docs.push(tmp_d);
			idx.push(tmp_i);
		}
	
	}

}



int main()
{
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		input();
		int ans = print_queue();
		printf("%d\n", ans);
	}
	return 0;
}

 

이 문제는 두 가지 방법으로 풀 수 있다. 

첫번째는 우선순위 종류가 많아도 적용할 수 있는 일반적인 방법이고, 두번째는 우선순위 종류가 적을때 (해당 문제의 경우 종류가 9개라 이 방법도 가능) 사용할 수 있다. 

 

 

먼저 "우선순위를 정렬하여 푸는 방법"을 알아보자. 

1. 문서의 우선순위를 담을 docs 큐와 인덱스를 담을 idx 큐를 생성하고, 루프를 한 번 돌려서 배열 D에 받아놓은 정보들을 큐에 옮겨준다. 

2. 우선순위가 높은 문서를 먼저 프린트하기 위해, #include <algorithm> 후 sort 라이브러리를 활용하여 배열 D를 내림차순 정렬해준다. 어차피 큐에 모든 정보를 옮겨놓았기 때문에, D의 순서를 바꿔주어도 무방하다.

compare() 함수는 여기에 쓰였다. 

3. 인덱스 M인 문서가 몇번째로 인쇄되는지 알기 위해 cnt 변수를 두고, 루프를 돌면서 우선순위가 높은 문서들을 먼저 출력한다. 

docs와 idx큐의 가장 앞에 있는 원소(각 tmp_d, tmp_i)를 꺼내어, tmp_d == D[i] 이면 현재 출력하려는 우선순위와 해당 문서의 우선순위가 동일한 것이므로 cnt 값을 증가시킨다(인쇄됨). 그런데 만약 tmp_i == M이면 우리가 찾던 그 문서이므로 cnt 값을 반환해준다. 인덱스가 같지 않다면, i 값을 증가시켜, 다음으로 출력할 우선순위를 탐색하도록 한다. 

한편 tmp != D[i]이면 현재 출력하려는 우선순위와 해당 문서의 우선순위가 동일하지 않은 것이므로, 출력하지 않고 큐의 가장 뒤로 보낸다.  

 

 

다음으로 "룩업테이블을 만들어서 푸는 방법"을 알아보자. 

사실 방법1과 로직은 동일하고(절대 쓰기 귀찮아서 아님..), 다만 이때는 우선순위가 가장 높(i == 9)을 때 룩업테이블의 값이 0이 아니라면 while 루프에 진입하여 구현해주었다. 그리고 해당 문서를 출력 시, lookup[i]의 값을 하나씩 줄여서 만약 0이 되면 루프를 빠져나오고 다음 우선순위를 탐색하도록 구현했다.  

이 방법으로 구현 시 중요한 것은 매 테스트케이스마다 룩업테이블을 초기화해줘야 한다는 것이다. 그래서 따로 init() 함수를 만들어 큐를 초기화할 때 같이 돌려주었다.