백준 정렬 1966번

안녕하세요. GDSC 웹 코어 멤버 송민선입니다.



먼저 문제 분석부터 진행해보겠습니다.

문제는

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

인데 문제 해석하는데 다소 오래걸렸습니다 ㅠㅠ

테스트 케이스도 이해하는데 오래 걸렸네요… 계속 해석하면서 2번 사항을 놓쳐서 이해를 못했어요…


Deque 활용

이번에 큐문제 풀면서 Deque에 대해 알게되었습니다.
다음 문제인 2164도 Deque로 풀면 아주 간단한 문제더라고요.
Deque를 사용하는 이유는 삽입 또는 제거를 할 경우, 일반적인 list를 사용하면 O(n)이 소요되는데,
Deque를 사용하면 O(1)이 걸린다고 합니다!!
간단히 사용방법을 보자면

from collections import deque

deque = deque([1,2,3,4])

deque.appendleft(5) #앞에 값 삽입
deque.append(0) #뒤에 값 삽입

deque.popleft() #앞에 값 삭제 후 출력
deque.pop() #뒤에 값 삭제 후 출력

풀이방법

import sys
from collections import deque

num = int(sys.stdin.readline())

for _ in range(num):
    n, target = map(int, input().split())
    priority = deque(map(int, input().split()))
    index = deque()
    count = 0

    for i in range(n):
        index.append(i)

    while True:
        if priority[0] == max(priority): # 만약 우선순위가 최상위 우선순위가 맞다면
            count += 1
            if index[0] == target: # 만약 내가 원하는 m 번째 일시 멈춤
                break
            priority.popleft()
            index.popleft()
        else:   # 아니면 뒤로 넘겻!
            priority.append(priority.popleft())
            index.append(index.popleft())
    print(count)

마무리

문제 이해하는데 오래걸렸네요. 간단하게 생각하면 앞에 값이 필요하면 바로 출력이고 아니면 뒤로 넘긴다!! 이걸 빠르게 캐치했어야 했네요.
그리고 우선순위를 어떻게 접목시킬것인지 생각을 잘 해야했네요.