[C++] 백준(BOJ) 1966 프린터

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

priority queue 문제이다 

주어진 테스트케이스에 대해서 대략적으로 출력순서가 어떻게 나오는지 나타냄

풀이 1(내 풀이) - 우선순위 큐 이용x

• PriorityQueue STL을 사용하지 않고 직접 구현하였다. 내 생각엔 STL을 사용하여 이보다 간단하게 풀이할 수 있는 방법이 있는 것 같다
• 디버깅이 중단점에 적중이 되지 않는 문제가 있었는데, 이를 F11 (Step Out) 키를 사용하여 해결하였다
• 아래 코드에선, priorityQueue 함수를 이용해 M 번째 인덱스의 출력시점의 횟수를 구한다

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int priorityQueue(int n, int m)
{
	int answer = 0;//출력
	int wonder = m; //궁금한 문서의 현재 인덱스 값;
	vector<int> priority; // n(N)개 문서의 중요도가 차례로 주어진 벡터
	for (int i = 0; i < n; i++)
	{
		int p;
		cin >> p;
		priority.push_back(p);
	}

	while (wonder != -1) //wonder 인덱스의 원소가 pop 되기 전까지
	{
		int a = priority.front();
		int max = 0;
		int newmaxIndex = 0;
		for (int i = 0; i < priority.size(); i++) //현재 priority vector 에서 가장 큰 중요도를 가진 값을 찾음
		{
			if (priority[i] > max) {
				max = priority[i];
				newmaxIndex = i;
			}
		}
		if (newmaxIndex == 0) //0번째 인덱스 원소의 값이 가장 큰 중요도를 가진 경우
		{
			priority.erase(priority.begin());
			answer++;
			wonder--;

		}
		else //0을 제외한 인덱스 원소의 값이 가장 큰 중요도를 가진 경우
		{
			priority.erase(priority.begin());
			priority.push_back(a);
			if (wonder != 0)
				wonder--;
			else //wonder == 0인 경우 && wonder의 원소 값보다 큰 중요도를 가진 원소가 다른 인덱스에 존재할 경우
			{
				wonder += priority.size() - 1;
			}
		}

	}
	return answer;

}
int main() {
	int testCase;
	int N, M; 
	/*
	* N : 문서의 개수
	* M : 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여있는지 나타내는 정수
	*/
	cin >> testCase;
	string ans="";
	for (int i = 0; i < testCase; i++)
	{
		cin >> N >> M;
		ans += to_string(priorityQueue(N, M));
		if (i < testCase - 1)
			ans += "\n";
	}
	cout << ans;
	return 0;
}

 

풀이2 (다른 사람) - 우선순위 큐 이용 o

https://lumir.tistory.com/62

• 위 블로그 참고하였음

/*우선순위 큐를 이용한 풀이*/
#include <iostream>
#include <queue>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int t;
	cin >> t;

	while (t--){
		int n, m;
		cin >> n >> m;

		//인덱스가 m인 문서가 몇번째로 인쇄되었는지 카운팅하는 변수
		int cnt = 0;

		queue<pair<int, int>> q;
		priority_queue<int> pq; //기본적으로 최대 힙 (부모 값 > 자식 값)

		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;

			q.push({ i,x }); //인덱스와 중요도
			pq.push(x); //중요도가 높은 순으로
		}

		while (!q.empty())
		{
			//큐의 front 원소를 꺼내서
			int idx = q.front().first;
			int priority = q.front().second;
			q.pop();

			//우선순위 큐의 top과 중요도가 일치하면
			if (pq.top() == priority) {
				pq.pop();
				cnt++; //문서 하나 인쇄할 때마다 증가

				//현재 문서의 인덱스가 m인 경우
				if (idx == m)
				{
					//몇번째로 인쇄되었는지 출력
					cout << cnt << "\n";
					break;
				}
			}
			else { //중요도가 높지 않으면 큐의 rear에 다시 push
				q.push({ idx, priority });
			}
		}


		
	}
	return 0;
}

---