[백준문제풀이] 1966 프린터 큐

 

풀이일시 : 2020-10-17

​

문제 :

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.

2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

​

​

입력 :

첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음줄에 N개 문서의 중요도가 주어지는데, 중요도는 1 이상 9 이하이다. 중요도가 같은 문서가 여러 개 있을 수도 있다. 위의 예는 N=4, M=0(A문서가 궁금하다면), 중요도는 2 1 4 3이 된다.

ex)

3 // test case 수

1 0 // 문서의 수, 몇번째로 인쇄됐는지 궁금한 문서가 현재 어떤위치에 있는지

5 // 중요도

4 2

1 2 3 4

6 0

1 1 9 1 1 1

​

​

출력 :

각 test case에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

ex)

1

2

5

​

​

풀이 :

자료구조, 큐를 이용한 시뮬레이션 문제이다.

 

1. 큐(queue) 만을 이용한 풀이

 

테스트 케이스를 거듭할때마다 array를 memset으로 초기화 해주어야한다.

그냥 정렬해서 뽑으면 될것같지만

만약 우선순위가 1 1 9 1 1 1 인데 그 중 궁금한문서는 5번 인덱스라면? 방법이 없을것이다.

그래서 중요도와 그 문서가 궁금한 문서인지의 여부를 pair 해주어 처리해야 할 것이다.

 

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

using namespace std;

queue <pair<int,int>> q;
int arr[101][2] = { 0, };

int main() {
	int tcase;

	cin >> tcase;
	for (int i = 0; i < tcase; i++) {//테스트케이스 수
		int N, M, s;
		int res1 = 0;
		int find;

		memset(arr, false, sizeof(arr));

		cin >> N >> M;
		for (int j = 0; j < N; j++) { //문서의 수만큼 반복
			cin >> s; //s를 받아서
			if (j == M) { //찾고자 하는 그 문서이면
				find = s; 
				q.push({ s,1 }); //s를 넣을때 1을 끼워넣는다. 바로 이 문서다!
			}
			else {
				q.push({ s,0 }); //찾는게 아니라면 0을 끼워넣는다.
			}
		}
		//큐의 사이즈를 다 돌아보며 큐 front 보다
		//현재보다 큰 수가 있다면 pop후에 다시삽입
		//큐가 빌때까지 반복해준다.

		while (!q.empty()) {
			int MAX = -1;
			int rfront = 0, front =0, size=0, result=0; //초기화

			for (int j = 0; j < q.size(); j++) { //큐 전체를 본다.
				int front = q.front().first; //문서 중요도 (1이면높은거)
				int second = q.front().second; //찾는문서인가 아닌가 (1or0)
				if (j == 0)  //처음만 rfront를 지정
					rfront = front;
				if (front > MAX) //MAX를 갱신할 상황이오면
					MAX = front; //MAX를 갱신해준다.				
				if (rfront < MAX) //MAX가 j=0이후 한번이라도 갱신되었다면. 즉 맨앞에있는게 가장 우선이 아니면
					size = 1;
				q.pop(); //꺼내고 
				q.push({ front,second }); //다시넣는다. 반복하는동안 다음것을 보기위해

                //q.size()-1까지 돌았으면 꺼내고 넣었으니 다시 원래의 큐가 되어있을것이다.
				if (j == (q.size() - 1)) { //다 돌고 마지막때
					if (size == 1){ //맨 첫번째가 가장 우선인 순위가 아니라면
						front = q.front().first;
						second = q.front().second;
						q.pop();
						q.push({ front,second }); //다시 뒤로넣는다.
					}
					else { //맨 첫번째에 있는게 가장 우선인 순위라면
						result = q.front().first;
						second = q.front().second;
						q.pop(); //뽑아서
						arr[res1++][second] = result; //출력해줄것이다.
					}
				}
			}
		}

		for (int j = 0; j < N; j++) {
			for (int z = 0; z < 2; z++) {
				if ((arr[j][z] == find)&&z==1) //하지만 찾고싶은 수가많다면은?
					cout << j + 1 << endl;		//0번째가 아니고 1번째니깐
			}
		}
	}
	return 0;
}

 

 

2. 우선순위 큐 (priority queue)를 이용한 풀이

 

각 test case에 대해 문서가 몇 번째로 인쇄되는지 출력해야한다.

중요도가 높은 문서를 priority queue에 넣어 자동으로 정렬되게 한다면 보다 쉽게 접근 할 수 있다.

#include <iostream>
#include <queue>
using namespace std;

int main(){
    int t;
    scanf("%d", &t);
    for (int case = 0; case < t; case++){
        int N, M,cnt = 0;
        queue <pair<int, int>> q;
        priority_queue <int> pq;
 
        scanf("%d %d",&N,&M); //문서의 수, 궁금한 문서가 현재 있는 위치
        for (int i = 0; i < N; i++){ 
            int a;
            scanf("%d", &a); //문서의 수만큼 반복하며 우선순위입력
            q.push({i,a}); //문서의 인덱스와 우선순위가 큐에 묶인다.
            pq.push(a); //우선순위는 pq에 들어간다.
        }
 
        while (!q.empty()){
            //여기서 front에 있는것은 우선순위가 가장 높은것일 것이다. && 먼저들어간거 우선
            int index = q.front().first; //현재 인덱스
            int value = q.front().second; //현재 문서 우선순위
            q.pop();
 
            if (pq.top() == value){ //큐에서 뽑아낸 문서의 우선순위가 pq의 우선순위가 같다면 뽑혀도 될 조건이다.
                pq.pop(); //pq도 뽑아낸다.
                cnt++; //그리고 count를 올린다.
                if (index == M){ //거기서 index가 찾고자하던 M과 같다면
                    printf("%d\n", cnt); //이게 우리가 찾는 count 값. 몇번째로 나온건지.
                    break;
                }
            }
            else { //맞지않는다면 뽑아낸 큐를 다시 넣어준다.
                q.push({ index,value });
            }
        }
    }
    return 0;
}

 

 

참고자료 : priority queue

dbstndi6316.tistory.com/31

[개념정리] priority_queue

참고자료 : memset

dbstndi6316.tistory.com/28

[개념정리] memset함수

참고자료 : pair

dbstndi6316.tistory.com/23

[개념정리] Pair