백준 알고리즘 1966번: 프린터 큐 [C++]

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

1966번: 프린터 큐

1. 코드

#include <iostream>
#include <algorithm>

using namespace std;

class quee {
	int f;
	int b;
	int* arr;
public:
	quee(int n) {
		f = 0;
		b = -1;
		arr = new int[n];
	}
	void push(int n) {
		arr[++b] = n;
	}
	int pop() {
		if (empty()) return -1;
		return arr[f++];
	}
	int size() {
		return b - f + 1;
	}
	int empty() {
		return (b - f) == -1;
	}
	int front() {
		if (empty()) return -1;
		return arr[f];
	}
	int back() {
		if (empty()) return -1;
		return arr[b];
	}
	~quee() {
		delete[] arr;
	}
};

bool compare(int i, int j)
{
	return i > j;
}
int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, check, t, cnt;
	cin >> t;
	while (t--) {
		cin >> n >> check;
		int temp;
		int* arr = new int[n];
		quee q(n * n);		//값 입력
		quee p(n * n);		//인덱스값 입력
		cnt = 0;			//인쇄한 순서
		for (int i = 0; i < n; i++)
		{
			cin >> temp;
			q.push(temp);
			arr[i] = temp;
			p.push(i);
		}
		sort(arr, arr + n, compare);		//내림 차순

		while (q.size() != 0)
		{
			while (arr[cnt] != q.front())	//입력한 값들 중 가장 큰 값인지 확인 아니라면 순서 뒤로 미루기
			{
				q.push(q.pop());
				p.push(p.pop());
			}
			q.pop();	//인쇄
			cnt++;
			if (p.pop() == check) {		//인덱스 값과 해당 인덱스 값이 맞는지 확인
				cout << cnt << endl;
				break;
			}
		}
		delete[] arr;
	}
	return 0;
}

(실행)

2. 풀이

해당 문제는 큐에 남아있는 수들 중 가장 큰 값이라면 제외하고 그렇지 않다면 순서를 제일 뒤로 미루며 이 때 알고자하는 인덱스값에 위치한 값이 몇 번째 순서로 제외됬는지 알려는 문제이다.

class quee {
	int f;
	int b;
	int* arr;
public:
	quee(int n) {
		f = 0;
		b = -1;
		arr = new int[n];
	}
	void push(int n) {
		arr[++b] = n;
	}
	int pop() {
		if (empty()) return -1;
		return arr[f++];
	}
	int size() {
		return b - f + 1;
	}
	int empty() {
		return (b - f) == -1;
	}
	int front() {
		if (empty()) return -1;
		return arr[f];
	}
	int back() {
		if (empty()) return -1;
		return arr[b];
	}
	~quee() {
		delete[] arr;
	}
};

위 코드와 같이 quee에 대한 코드를 먼저 만듭니다.

cin >> t;
while (t--) {
	cin >> n >> check;
	int temp;
	int* arr = new int[n];
	quee q(n * n);		//값 입력
	quee p(n * n);		//인덱스값 입력
	cnt = 0;		//인쇄한 순서

그리고 테스트 횟수를 입력하고 그 횟수만큼 반복고, 인쇄 갯수와 확인하고자 하는 수를 입력한 뒤 큐를 2개를 생성한다. 하나는 인덱스값을 다른 하나는 해당하는 값을 저장한다. 그리고 arr을 동적할당하여 해당하는 값을 넣는다. arr은 제일 큐에서 제일 큰 수가 무엇인지 시켜주는 역할을 한다.

for (int i = 0; i < n; i++)
{
	cin >> temp;
	q.push(temp);
	arr[i] = temp;
	p.push(i);
}
sort(arr, arr + n, compare);		//내림 차순

그리고 반복문을 이용하여 값들을 넣어주며 arr을 내림차순으로 정렬한다.

while (q.size() != 0)

큐가 비어있을 때까지 반복한다.

while (arr[cnt] != q.front())	//입력한 값들 중 가장 큰 값인지 확인 아니라면 순서 뒤로 미루기
{
	q.push(q.pop());
	p.push(p.pop());
}

큐에서 저장된 수들 중 가장 큰 값인지 검사 후 아니라면 같을 때까지 큐의 값과 인덱스값을 제일 뒤로 놓는다.

q.pop();	//인쇄
cnt++;
if (p.pop() == check) {		//인덱스 값과 해당 인덱스 값이 맞는지 확인
	cout << cnt << endl;
	break;
}

그렇다면 가장 큰 값이 나오게 되므로 해당하는 값을 큐에서 제외한 뒤 제외한 회수를 cnt를 이용하여 측정한다. 그리고 인덱스값 또한 제외하는데 그 값이 알고자하는 순서와 맞는지 검사후 맞다면 cnt를 출력 후 반복문을 종료한다.

		}
		delete[] arr;
	}
	return 0;
}

그리고 arr의 동적할당을 해제한 뒤 프로그램을 종료해준다.

3. 느낀점

이 문제를 풀면서 컴파일러가 정말 많은 도움이 되었다. 특히 논리적 오류는 머리로 생각해도 알 수 없기에 이렇게 눈으로 볼 수 있다는게 정말 좋은 것 같다.