백준 1966번 "프린터 큐"

백준 1966번 “프린터 큐”

Question:

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를
인쇄 명령을 받은 ‘순서대로’,
즉 먼저 요청된 것을 먼저 인쇄한다.
여러 개의 문서가 쌓인다면 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번째로 인쇄되게 된다.

Input:

첫 줄에 테스트케이스의 수가 주어진다.
각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과,
몇 번째로 인쇄되었는지 궁금한 문서가
현재 Queue에서 몇 번째에 놓여 있는지를 나타내는
정수 M(0 ≤ M < N)이 주어진다.
이때 맨 왼쪽은 0번째라고 하자.
두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다.
중요도는 1 이상 9 이하의 정수이고,
중요도가 같은 문서가 여러 개 있을 수도 있다.

Output:

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

Restriction:

시간제한:
2 초

Example Case: Input case 1:

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

Output case 1:

1
2
5

풀이 과정: 이 문제는,
중요도를 나타내는 리스트와 데이터를 담은 큐의 성질을 이용한 문제이다.

처음 문제를 이해하고 나면
정수에 대해 입력을 받고나서 “중요도”에 대해 생각하게 된다.
우리가 구하여야하는 값은 정수 최대값에 따른 특정 문서의 출력 순서이다.

따라서,
문제를 풀기 위해 중요도를 담은 또 다른 하나의 리스트가 필요한데,
여기서 우리가 알고 싶은 특정 문서의 위치에 리스트 값을 1로 설정한다.
(나머지는 0으로 초기화.)

가장 중요한 요소는
덱에서 popleft() + append() 연산을 하면서 탐색하다 최대값을 만났을때,
그 element가 중요도 “1”인 특정 문서인지 판단이 필요하다.
그러므로, 조건은 크게

“덱에서의 정수 element 중 가장 큰 값인가?”

“그렇다면,그 element에 대응하는 중요도 리스트의 element도 “1”인가?

…로 나뉜다.
위 두 조건을 모두 해당 하였을 때,우리가 찾는 출력 값이 나온다.

예제의 연산과정을 그려보았다.

중요도 리스트는 항상 출력대상과 대응된다는 것을 생각하자.

아래는 python으로 작성한 코드이다.

from collections import deque
import sys

t = int(sys.stdin.readline())
for _ in range(t):
    N,target = map(int,sys.stdin.readline().split())
    dataq = deque(map(int,sys.stdin.readline().split()))
    index = [0 for _ in range(N)] #중요도 리스트 초기화
    index[target] = 1 #덱이랑 대응되는 리스트,우리가 출력해야할 element 위치
    cnt = 0
    while 1:
        if dataq[0] == max(dataq): #덱의 첫번째 element가 최대값일때,
            if index[0] == 1: #중요도 1순위(출력대상)
                break
            else: #정수 최대값은 맞지만,중요도 1순위는 아닐때,
                dataq.popleft() #맨 앞 element 삭제
                index.pop(0) #중요도 리스트에서도 맨 앞 element 삭제
                cnt += 1 #연산 count 증가
        else:
            dataq.append(dataq.popleft()) #탐색 진행
            index.append(index.pop(0)) #중요도 리스트도 대응
    print(cnt+1) #찾았을 경우 +1

• 백준
• 문제풀이