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

백준 1966 : 프린터 큐

 

문제 링크

www.acmicpc.net/problem/1966

1966번: 프린터 큐

 

 

문제 내용

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

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

몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어지고 이때 맨 왼쪽은 0번째라고 하자.

두 번째 줄에는 N개의 문서의 중요도가 차례대로 주어진다.

 

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

 

 

Idea

처음에는 c언어로 해서 linked list를 이용하여 큐를 만들려고 했는데 (귀찮아서....)

c++의 vector를 이용해 큐처럼 만들었다.

단순히 우선순위를 고려하여 구현하면 되는 문제였다.

 

첫 번째 요소의 우선순위가 제일 크지 않을 때

• 큐의 제일 뒤로 옮김

 

첫 번째 요소의 우선순위가 제일 클때

• 찾고자 하는 문서면 출력
• 아니라면 요소를 뽑아내고 다시 탐색

 

 

Code

#include <stdio.h>
#include <vector>
using namespace std;
 
int main() {
    int T;
    int n, m;
 
    //큐를 위한 벡터
    vector<pair<int,int>> v;
 
    //T개의 테스트케이스
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        scanf("%d %d", &n, &m);
        
        //각 문서에 우선순위 삽입
        int priority;
        for (int i = 0; i < n; i++) {
            scanf("%d", &priority);
            v.push_back(make_pair(priority, i));
        }
        
        //해당 문서가 몇 번째로 인쇄되는지 찾기
        int cnt = 1;
        while (1) {
 
            //큐가 비어있다면 cnt 출력하고 종료
            if (v.empty()) {
                printf("%d\n", cnt);
                break;
            }
 
            bool b = true;
            int size = v.size();
 
            //큐의 첫번째 요소의 우선순위가 제일 큰지 검사
            for (int i = 1; i < size; i++) {
                //우선순위가 크지 않다면
                //뒤로 넣기
                if (v[0].first < v[i].first) {
                    v.push_back(make_pair(v[0].first, v[0].second));
                    v.erase(v.begin());
                    b = false;
                    break;
                }
            }
 
            //첫 번째 요소가 제일 크다면
            if (b) {
                //찾고자 하는 문서라면
                //cnt 출력 및 종료
                if (v[0].second == m) {
                    printf("%d\n", cnt);
                    break;
                }
                //아니라면 첫 번째 요소 지우고
                //cnt++
                else {
                    v.erase(v.begin());
                    cnt++;
                }
            }
        }
        v.clear();
    }
 
    return 0;
}