BOJ 1966 프린터 큐

문제출처 : https://www.acmicpc.net/problem/1966

1. 문제요약

- 중요도에 따라 인쇄순서를 결정하고 특정 문서가 몇번째 출력되는가?

- 문서의 수 N <= 100, 0 <= 위치 M < N

2. 접근방법

- 일단 N이 얼마 안되기 때문에 브루트 포스

- 모든 문서가 큐에 저장

- 큐에 첫번째 문서가 출력 대상이 아니라면 뒤로 보냄

- 출력 대상이라면 출력

3. 시간복잡도

- Queue나 배열 하나만 쓴다면 N^3,

  출력 대상을 찾는데 하나의 문서와 모든 문서를 비교 해야 하므로 N^2, 

  모든 문서의 개수가 N 이므로 N^3

- Priority_Queue 라던가 가중치를 가지고 있다면,

  하나의 문서를 찾는데 N, 문서 전체의 개수가 N 이므로 N^2

4. 회고

- 배열을 큐처럼 만들어서 출력 대상이 아니면 배열 뒤에 붙이는 방식인 경우 최소 100 * 101 / 2 = 5050 이상 사이즈가 필요

- 인덱스만 가지고 움직인다면 배열 사이즈는 N이면 됨

  출력한 놈을 다시 출력하는 논리적 오류가 발생

  이런거 신경 안쓸려면 index를 출력한놈은 건너 뛰게 만들어야함

- 문서 번호와 문서 중요도를 보관해야 함

- 배열로 구현 했을 때 한칸씩 당기지 않으면 출력 했는지 안했는지 체크가 필요

- Queue 자료구조를 쓴다면 front를 뺄 때, 다른 자료와의 중요도를 비교할 수 있는 수단이 필요함

  하나씩 빼서 비교하던가 아니면 Priority_Queue나 중요도를 저장하고 있는 다른 배열과 비교가 필요

소스코드 : N^3

#include<iostream>
using namespace std;

int main(void){
	int t;
	cin >> t;
	while (t--){
		int n, m, q[101], check[101] = { 0 };
		cin >> n >> m;
		for (int i = 0; i < n; i++)
			cin >> q[i];

		int index = 0, cnt = 1;
		while (cnt <= n){
			if (index == n) index = 0;

			int i = 0;
			for (; i < n; i++){
				if (!check[i] && q[index] < q[i])
					break;
			}
			// !check[index]가 없다면 출력한 놈을 다시 출력하게 함
			// 예제에서 정답은 맞아도 중간 값이 틀림 => 결국은 틀림
			if (!check[index] && i == n){
				check[index] = cnt;
				cnt++;
			}

			index++;
		}

		cout << check[m] << "\n";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]