[Algorithm] [Python] 백준/BOJ - 1966_프린터 큐

1966 - 프린터 큐

---

INDEX

---

• 문제
• 입력
• 출력
• 예제 입출력
• 제출 코드
• 문제 풀이

 

문제

---

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

현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 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이 된다.

 

출력

---

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

 

예제 입출력

---

제출 코드

---

from sys import stdin

TK = int(stdin.readline())

for _ in range(TK):                     # 테케 만큼 반복한다.
    # N : 문서의 수, M : 몇번쨰에 인쇄되는지 궁금한 문서의 idx
    N,M = map(int, stdin.readline().split())       
    priority = list(map(int, stdin.readline().split()))
    chk = [0 for _ in range(N)]

    chk[M] = 'T'
    target = priority[M]        # 타겟 설정
    printed_cnt = 1

    while priority:
        if priority[0] == max(priority):        # 만일 현재 값이 출력대상이라면
            if chk[0] == 'T':                   # 내가 원하는 것이 맞는지 인덱스로 확인
                print(printed_cnt)
                break
            else:
                priority.pop(0)                 # 출력 대상이 타겟값이 아니면 그냥 출력하고 카운팅
                chk.pop(0)
                printed_cnt += 1

        else:                                   # 현재 값이 출력대상이 아니라면
            priority.append(priority.pop(0))    # 0번쨰 원소를 뽑아서 제일 뒤로 보낸다.
            chk.append(chk.pop(0))

문제 풀이

---

본 문제는 Queue 문제로 분류되어있으며 Queue의 기본적인 성질을 알고 있는지 묻는 문제이다.

우리가 정확히 원하는 값을 알아내기 위해서는 중요도 하나로 해당 문제를 풀어내기에는 다소 어려웠다.

처음에는 중요도 만을 가지고 답을 구하려 했으나, 동일한 중요도를 갖는 원소가 여러개인 경우, 테스트케이스 3번) 1 1 9 1 1 1 와 같은 경우에는 정확히 우리가 원하는 값의 위치를 파악하기는 힘들다.

정답을 구하기 위해선 크게 2가지 조건을 필터링 해야한다.

1. 현재 값이 큐 내에서 가장 높은 중요도 값을 갖는가? -> 출력 대상인가?
2. 만일 가장 높은 중요도 값을 갖는다면, 내가 원하는 값이 맞는가?

필자는 해당 문제는 중요도와 더불어 인덱스 값을 활용하여 풀어냈다.

전달받은 문서의 수 N의 길이를 갖는 배열(chk)을 만들어 우리가 원하는 M번쨰 원소를 식별 해낼수 있도록 'T' 값으로 초기화 하였다.

이후, 중요도가 담긴 priority 배열을 통해 while loop를 실행한다.

만일 priority[0]의 값이 max(priority) 값과 동일하다면, 즉 현재의 문서가 큐의 문서중 가장 높은 중요도값을 갖는다면 첫번쨰 조건을 만족한다.

이후, 내가 원하는 값이 맞는지 확인하기 위하여 chk[0] == 'T' 조건을 통해 확인한다.

위 두 조건을 만족한다면 우리가 원하는 값이 된다.

만일 출력 대상은 맞으나 우리가 원하는 값이 아니라면 현재 문서의 중요도 값, 인덱스 값을 각각의 배열에서 pop 한다.

만일 출력 대상 또한 아니라면 현재 문서의 중요도 값과 인덱스 값을 각각의 배열 제일 뒷부분으로 보낸다.