BOJ - 1966 프린터 큐 해결 전략 (C++)

• 문제 링크
  백준 1966번 - 프린터 큐

해결 전략

  본 문제는 쉬운 문제이다. 다만, 구현 측면에서 중요한 스킬이 있어 포스팅하기로 했다. 우선, 문제를 해결하는 알고리즘적 측면에서는, 직관적으로 해결하면 된다. 선형 자료구조의 맨 앞 요소보다 우선순위가 높은 요소가 있으면 맨 앞 요소를 Pop해서 맨 뒤로 Push하면 된다.

  이때, '맨 앞보다 우선순위가 높은 요소가 있는지'를 찾는 부분을 어떻게 구현하느냐가 원래같으면 문제 풀이의 핵심 부분이될터이지만, 본 문제에선 최대 입력이 100개이기 때문에 사실 100개 전체를 2000000번 이상 순회할 일은 전무하므로 그냥 Naive하게 선형 순회로 구성하면 된다. 이 아이디어를 기반으로 간단하게 구현할 수 있다.

  구현 과정에서의 주요 스킬은 다음과 같다.

1) queue나 vector와 같은 stl은 pop이나 push의 위치가 한정적이므로 Doubly Linked List를 제공하는 list 헤더를 전처리하는 것이 합리적이다.

2) 대신, list를 택할 경우, 선형 순회를 구성할 때에는, iterator를 사용해야한다. list는 인덱스 참조가 제공되지 않기 때문이다. 따라서, 아래와 같은 for문이 중요하다.

for (list<type_name>::iterator iter = lt.begin(); iter != lt.end(); iter++)

  자주 사용하는 C++의 STL들의 각각의 특성을 인지하는 것, 그리고 vector와 list에서 iterator를 사용하는 방법은 중요한 PS 스킬이다. 앞으로도 이를 잘 기억해 애용하도록 하자.

  아래는 코드이다.

#include <iostream>
#include <list>
// BOJ - 1966 Printer Queue
using namespace std;

typedef struct _node {
	int index;
	int prior;
}Node;

list<Node> q;

int solve(int m) {
	int printCnt = 0, tempPrior;
	bool popflag;

	while (!q.empty()) {
		tempPrior = q.front().prior; popflag = false;

		for (list<Node>::iterator iter = q.begin(); iter != q.end(); iter++) {
			if ((*iter).prior > tempPrior) {
				q.push_back(q.front());
				q.pop_front();
				popflag = true;
				break;
			}
		}

		if (!popflag) {
			printCnt++;
			if (q.front().index == m) return printCnt;
			q.pop_front();
		}
	}
}

int main(void) {
	int t, n, m, p;
	Node temp;

	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			cin >> p;
			temp.index = i; temp.prior = p;
			q.push_back(temp);
		}

		cout << solve(m) << '\n';
		q.clear();
	}

	return 0;
}