문제 요약
문제
백준 1966 프린터 큐
문서를 중요도에 따라 순서대로 인쇄하는 프린터 큐를 조건에 맞게 구현하라.
입력
첫 줄에 테스트케이스의 수
두 번째 줄부터 두 줄씩 각 테스트케이스 입력
각 테스트케이스의 첫 번째 줄은 문서의 개수와 인쇄 순서를 알아낼 문서의 위치 번호, 두 번째 줄은 대기중인 문서의 중요도 수열
문서 위치 번호는 0번부터 시작하며 중요도는 1 이상 9 이하의 정수이고 중복 가능하다.
출력
줄마다 각 테스트케이스에 대해 문서가 몇 번째로 인쇄되는지 출력
문제 풀기
첫 번째 시도
방법
STL의 우선순위 큐를 사용했고, 큐에 각 인쇄물의 중요도와 대기열 순서를pair<int, int>로 넣었다.결과 : 예제 틀림
사유
중요도는 같고 대기열 순서가 다른 인쇄물의 인쇄 순서를 맞히지 못한다.코드 설명
pair<int, int>에 입력된 정수의 순서는 <중요도, 대기열 순번>이다.
파일 입출력 연습을 겸하여ifstream를 사용했으나 이를cin으로 대체하고, 문제 풀이 함수에 전달되는 파라미터를 지우면 백준에 제출할 수 있다. 또한 빠른 예제 채점을 위해 매 테스트케이스마다 자동으로 정답을 확인하도록 했다.코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
#include <iostream> #include <fstream> #include <string> #include <queue> #include <utility> using namespace std; const string in_file_route = "example_input.txt"; // 예제 입력 텍스트 파일 const string out_file_route = "example_output.txt"; // 예제 정답 텍스트 파일 int when_print(ifstream* inputs); // 문제 풀이 함수. 파일 입출력을 위해 ifstream 객체 포인터 전달. int main() { // 빠른 입출력 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ifstream input_file{ in_file_route }; ifstream output_file{ out_file_route }; int t; // 테스트케이스 개수 input_file >> t; for (int i = 0; i < t; i++) { int ans = when_print(&input_file); // 테스트케이스 풀이 결과 반환 int correct; // 예제 정답 output_file >> correct; cout << ans << "\n"; if (ans == correct) // 정답 확인 cout << "answer = " << correct << "\ncorrect\n\n"; else cout << "answer = " << correct << "\nwrong\n\n"; } // 파일 사용 후 반드시 close input_file.close(); output_file.close(); return 0; } int when_print(ifstream* inputs) { int n, m; int cnt = 0; priority_queue<pair<int, int>> pq; *inputs >> n >> m; for (int i = 0; i < n; i++) { // 인쇄 대기열 입력 int num; *inputs >> num; pq.emplace(num, i); } for (int i = 1; i <= n; i++) { // 인쇄 시작 pair<int, int> current_page = pq.top(); if (current_page.second == m) { // 원하는 인쇄물이 인쇄됨 cnt++; break; } else { // 원하는 인쇄물이 아님 pq.pop(); cnt++; } } return cnt; // 결과 반환 }
두 번째 시도
방법
덱에pair<int, int>로 문제에서 주어진 인쇄 대기열을 그대로 저장하고(pair<중요도, 순서>), 우선순위 큐에는 인쇄물의 중요도만을 저장한다. 이후 큐의 top과 덱의 front를 비교해 중요도가 같다면 출력하며 출력 횟수를 세고, 만약 출력한 인쇄물의 인쇄 대기열 순서가 문제에서 지정한 순번의 인쇄물과 같다면 세어 두었던 출력 횟수를 반환한다.결과 : 통과
설명
우선순위 큐만 사용하면 틀리는 이유가 있다. 우선순위 큐는 디폴트로 내림차순 정렬을 하는데, 앞서 시도한 방법처럼pair<int, int>를 사용하고first요소가 중복되는 경우가 생긴다면second요소도 같이 비교하여 내림차순 정렬을 한다. 대기열 번호는 오름차순으로 부여했기 때문에 원래 대기열의 역순으로 정렬이 되어버려 인쇄 순서가 달라진다. 우선순위 큐가 대기열 번호를 정렬 기준으로 삼지 않게 처음부터 중요도만 입력하면 이런 문제가 발생하지 않고, 대신 원래의 인쇄 대기열을 따로 저장해야 한다. 또한 인쇄 우선순위가 1순위가 아닌 문서가 대기열의 맨 뒤로 갈 수 있도록 하기 위해 양방향 출입이 가능한 덱으로 인쇄 대기열을 저장했다.
첫 번째 시도와 달라진 부분이 하나 더 있는데, 인쇄물 인쇄 반복문이for에서while로 바뀌었다. 그 이유는 대기열 순번이 우선순위 순번과 다를 경우 인쇄를 하지 않고 넘어가야 했기 때문이다.for의 반복 횟수는 전체 인쇄물의 개수와 같고, 이는 모든 인쇄물이 한번에 인쇄되는 것을 전제로 한다. 그렇기 때문에 인쇄물이 대기열에 다시 추가될 경우 해당 문서는 인쇄될 수 없다. 그런 경우를 방지하기 위해 큐가 완전히 비워질 때까지 실행하는 조건으로while을 사용했다.코드 - 깃허브에서 보기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
#include <iostream> #include <queue> // 큐, 우선순위 큐 #include <utility> // pair #include <deque> // 덱 using namespace std; int when_print(); // 문제 풀이 함수 int main() { // 빠른 입출력 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; // 테스트케이스 개수 cin >> t; for (int i = 0; i < t; i++) { int ans = when_print(); // 테스트케이스 연산 결과 반환 cout << ans << "\n"; } return 0; } int when_print() { int n, m; int cnt = 0; deque<pair<int, int>> printer; // 실제 프린터 대기열 priority_queue<int> pq; // 우선순위 대기열 cin >> n >> m; for (int i = 0; i < n; i++) { // 대기열 입력 int num; cin >> num; printer.emplace_back(num, i); pq.push(num); } while (!pq.empty()) { // 인쇄물이 남지 않을 때까지 인쇄 pair<int, int> ptr_curr_page = printer.front(); int pq_current_page = pq.top(); if (ptr_curr_page.first == pq_current_page) { // 현재 인쇄 대기 인쇄물의 중요도가 실제 대기열과 우선순위 대기열에서 동일할 때 출력 cnt++; pq.pop(); printer.pop_front(); if (ptr_curr_page.second == m) // 인쇄한 인쇄물의 순번이 문제에서 지정한 것과 같다면 정답 반환 break; } else { // 올바르지 않은 인쇄물은 대기열 맨 뒤로 보냄 printer.pop_front(); printer.push_back(ptr_curr_page); } } return cnt; }