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

deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_back(3);

문제

문제 분석

- 문제에서 주어진 조건대로만 잘 구현하면 된다.

- 앞 뒤로 데이터가 push 되기 때문에 deque 자료구조를 사용한다.

- N이 최악의 경우 100이므로 시간 복잡도를 크게 신경쓰지 않아도 된다. O(N^4)까지 괜찮다.

정답 코드

// 풀이 시간 : 41분 28초
#include <iostream>
#include <deque>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	int testcase;
	cin >> testcase; // 1번째줄 : testcase 수
	for (int i = 0; i < testcase; i++) {
		deque<pair<int, int>> dq; // (중요도, 문서 번호)
		int N, find_document_num; 
		cin >> N >> find_document_num; // 2번째줄 : 문서 개수 , 찾고자 하는 문서 번호
		// 3번째줄 : 문서의 중요도 정보 넣기
		for (int document_num = 0; document_num < N; document_num++) {
			int priority; // 중요도
			cin >> priority;
			dq.push_back(make_pair(priority, document_num));
		}

		// 찾고자 하는 문서가 몇 번째에 나오는지 찾기
		int max_priority = -1; // 중요도의 최댓값
		int ans = 0; // 정답
		while (1) {
			// 아직 max_priority가 정해지지 않은 경우 -> deque에 남은 것중 중요도의 최댓값을 구한다.
			if (max_priority == -1) { 
				for (auto iter = dq.begin(); iter != dq.end(); iter++) {
					max_priority = max_priority > iter->first ? max_priority : iter->first;
				}
			}
			// 현재 뽑을 것이 최대의 우선순위를 가지고 있는 경우 -> 정답 출력
			if (dq.front().first == max_priority) {
				// 찾고자 하는 문서 번호였을 때
				if (dq.front().second == find_document_num) {
					cout << ans + 1 << "\n";
					max_priority = -1; // 다시 중요도의 최댓값을 찾는다.
					break;
				}
				// 찾고자 하는 문서 번호가 아니었을 때 -> 뽑는다.
				else {
					dq.pop_front();
					ans++;
					max_priority = -1; // 다시 중요도의 최댓값을 찾는다.
				}
			}
			// 현재 뽑을 것이 최대의 우선순위를 가지고 있지 않은 경우 -> 다시 맨 뒤로 보낸다.
			else if (dq.front().first != max_priority) {
				dq.push_back(dq.front());
				dq.pop_front();
			}
		}
		
	}

	return 0;
}

 

교훈점

- 순서가 정해져 있고 앞 뒤로 데이터를 삽입해야 할 경우 deque 자료구조를 사용하면 용이하다.

- front와 back을 헷갈리지 말자. push_back을 한 기준으로 front는 가장 먼저 들어온 것이고, back은 가장 나중에 들어온 쪽이다.

즉, push_back은 back 쪽에서 들어온다는 뜻이다.

deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_back(3);

위 코드를 그림으로 나타내면 아래와 같다.

 

dq.push_back(4);

위 연산을 수행하면 다음과 같이 바뀐다.