개요

백준 1966번: 프린터 큐

• 입력
  첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

  테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

• 출력
  각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

접근 방법

1. 전체 중요도를 알아야하는 문제에서 큐만을 가지고 풀기엔 어렵기 때문에, 전체 중요도를 저장할 배열을 따로 선언한 후, 해당 배열을 정렬해줘서 중요도 순서를 파악하게끔 하였다.

코드

# include<iostream>
# include<queue>
# include<algorithm>

using namespace std;

struct document {
	int index;
	int priority;
};
queue<document> q;
//전체우선도 저장용 배열
int prioritySave[101];
int N=0;

//큐 초기화
void initQ() {
	while (!q.empty()) {
		q.pop();
	}
}

//타겟 문서가 뽑히는 순서 출력
void printDocumentOrder() {
	//각 테케의 문서갯수, 타겟문서의 index, 각 문서의 중요도, 중요도배열에서 index용도로 사용할 cnt변수, 출력할 답
	int documentAmount,targetDocumentNum=0,elemPriority=0,cnt=0,ans=1;
	cin >> documentAmount >> targetDocumentNum;
	for (int i = 0; i < documentAmount; i++) {
		cin >> elemPriority;
		prioritySave[i] = elemPriority;
		document d = { i,elemPriority };
		q.push(d);
	}
	//중요도 배열 정렬
	sort(prioritySave, prioritySave+documentAmount,greater<int>());

	while (1) {

		//큐의 front값의 우선순위가 제일 높은게 나올때까지 front의 원소를 뒤로 push
		while (q.front().priority != prioritySave[cnt]) {
			document tmp = q.front();
			q.pop();
			q.push(tmp);
		}
		//큐의 front값의 index가 타겟문서의 index랑 같다면 답이므로 출력
		if (q.front().index == targetDocumentNum) {
			cout << ans<<'\n';
			return;
		}
		//front원소의 우선순위가 제일 높지만 타겟 문서가 아니라면 
		else {
			//해당 원소 pop해준 후,
			q.pop();
			//답++,
			ans++;
			//중요도배열index++
			cnt++;
		}
	}

}

void solution() {
	for (int i = 0; i < N; i++) {
		initQ();
		printDocumentOrder();
	}

}

void input() {
	cin >> N;
}

int main() {
	input();
	solution();
}

priority_queue 를 사용한 코드

배열을 사용한 후 정렬하는 부분을 priority_queue를 사용시 높은값 부터 알아서 front에 넣어준다.

#include<iostream>
#include<queue>

using namespace std;

//index, cost
queue<pair<int,int>> q;
//priority_queue에서 두번째값 기준으로 내림차순으로 정렬할 때, 구조체를 따로 만들고 안에 비교함수넣어야함.
struct comp {
	bool operator()(pair<int, int> a, pair<int, int> b) {
		if (a.second != b.second) {	
			return a.second < b.second;
		}
		else {
			return a.first < b.first;
		}
	}
};

//priority_queue
priority_queue<pair<int,int>,vector<pair<int,int>>,comp> pq;

void init() {
	while (!q.empty())
		q.pop();
	while (!pq.empty())
		pq.pop();
}

int main() {
	int N, docAmount, targetDocIndex = 0,cnt=0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cnt = 0;
		init();
		cin >> docAmount >> targetDocIndex;
		for (int j = 0; j < docAmount; j++) {
			int cost = 0;
			cin >> cost;
			q.push(make_pair(j,cost));
			pq.push(make_pair(j,cost));
		}
		while (1) {
			//q의 중요도가 pq의 탑(제일 높은 중요도)보다 작다면
			while (q.front().second < pq.top().second)
			{
				//큐의 앞값 뒤로 넣어주고
				q.push(q.front());
				//앞값 삭제
				q.pop();
			}
			if (q.front().first == targetDocIndex) {
				cnt++;
				cout << cnt<<'\n';
				break;
			}
			//반복문이 위의 if문에 안걸리고 끝났다면 앞값은 지워야하므로 pop
			q.pop();
			pq.pop();
			cnt++;
		}

	}
}

문풀후생

priority_queue를 거의 안사용하다보니 비교함수 작성하는데 좀 애를 먹었다.