[백준] B1966 프린터 큐

오랜만에 백준으로 간단히 실버3 자료구조 문제를 풀어봤다.

[백준 1966번 프린터 큐 실버3]
https://www.acmicpc.net/problem/1966

문제

---

프린터의 가장 앞 쪽에 위치한 문서는 출력될 문서로 자신의 뒤에 위치한 나머지 문서들보다 큰 중요도를 가졌을 경우 출력되고, 그렇지 않을 경우 맨 뒤로 재배치된다.

M번째로 입력된 문서가 몇 번째로 출력되는지 알고자 하는 문제이다.

1. heap[0]에 위치한 문서와 heap[1]~heap[max] 문서들의 중요도를 비교한다.
2. heap[0] 문서보다 중요도가 높은 문서가 존재할 경우 heap[0] 문서를 맨 뒤로 옮긴다.
3. heap[0] 문서의 중요도가 가장 높을 경우 heap에서 제거해준 후 max를 감소시킨다.
4. 해당 과정을 M번째 문서가 나올 때까지 count 값을 증가시키며 반복해주면 된다.

입력될 문서의 최대 개수가 100개이므로 O(n^2)의 시간 복잡도를 가진다.

조건이 널널해서 간단하게 풀 수 있었다.

//flag: 알고자 하는 문서 위치
//max_index가 1이면 바로 출력
if (max_index == 1)
	return 1;
//flag 위치 찾기
while (1) {
	bool check = false;
	Node first_node=heap[0];
	//더 큰 문서가 있는지 확인
	for (int i = 1;i < max_index;i++) {
		//남은 문서 중 하나라도 더 클 경우 뒤로 보냄
		if (first_node.data < heap[i].data) {
			//뒤로 보내기
			//cout<< first_node.index <<" " << first_node.data << " 뒤로 보내기" << endl;
			heap.push_back(first_node);
			heap.erase(heap.begin());
			check = true;
			break;
		}
	}
	//더 큰 문서가 없는 경우 pop
	if (!check) {
		heap.erase(heap.begin());
		max_index--;
		//cout << first_node.index << " " << first_node.data << " 출력" << endl;
		print_count++;
		if (first_node.index == flag) {
			//cout<<print_count<<"번째 출력" << endl;
			//cout<<first_node.index<<"번째 문서" << endl;
			return print_count;
		}
	}
	
}