[BOJ] 1966 프린터큐

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

Note

우선순위 가 포함된 큐 이다. 말 그대로 우선순위 큐를 이용하는 문제다.
Max Heap을 이용하면 쉽게 풀리는 문제다.
이번 문제는 Max Heap을 이용하지 않고 문제 자체에 충실하게 구현했다.

무한루프를 사용하지 않고 만들고 싶었지만 최근 결과를 보니 거의다 무한루프를 사용..
정답률도 높고 하니 한번쯤은 무한루프를 사용해도 괜찮다 생각해서 사용했다.

알고리즘

1. 개수, 목표 번호, 우선순위를 입력 받는다.
2. 다음으로 높은 우선순위를 결정하는데 사용할 출력 확인 배열을 생성한다.
3. Queue에 0부터 n - 1까지 순서대로 push 한다
4. 최 우선순위인 값이 출력이 되면 최 우선순위를 갱신한다. 최 우선순위가 아닌경우 Queue에 다시 넣는다.
5. 목표값이 나올 때 까지 계속 반복한다.
6. 나온 결과값에 대해 출력한다.

소스코드

#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

int getVeryImportant(int& n, int priority[100], bool out[100])
{
	int top = 0;

	for (int i = 0; i < n; i++)
		if (!out[i] && top < priority[i])
			top = priority[i];

	return top;
}

int solution(int n, int pos, int priority[100])
{
	bool isOut[100];
	memset(isOut, false, sizeof(isOut));
	int res = 1;
	int veryImportant = getVeryImportant(n, priority, isOut);
	int now = 0;
	queue<int> q;

	for (int i = 0; i < n; i++)
		q.push(i);

	while (true)
	{
		now = q.front();
		q.pop();

		if (now == pos && veryImportant == priority[now])
			break;

		if (veryImportant == priority[now])
		{
			res++;
			isOut[now] = true;
			veryImportant = getVeryImportant(n, priority, isOut);
		}
		else
			q.push(now);
	}

	return res;
}

int main()
{
	int tcc;

	cin >> tcc;

	for (int i = 0; i < tcc; i++)
	{
		int n, pos;
		int priority[100];
		cin >> n >> pos;
		for (int j = 0; j < n; j++)
			cin >> priority[j];

		cout << solution(n, pos, priority) << '\n';
	}

	return 0;
}

2019-01-10 10:30:00에 Tistory에서 작성되었습니다.