[백준] 1966 - 프린터 큐

문제

문제 : https://www.acmicpc.net/problem/1966

일반적으로 프린터 기기는 인쇄 명령을 받은 순서대로 문서를 인쇄한다. 그런데 최근 상근은 다음과 같이 동작하는 새 프린터 소프트웨어를 개발했다.

1. 프린터 큐 내 맨 앞에 있는 문서의 중요도를 확인한다.

2. 나머지 문서 중 현재 문서보다 높은 중요도의 문서가 있으면, 이 문서는 인쇄하지 않고 큐의 맨 뒤로 재배치한다. 그렇지 않으면 현재 문서를 인쇄한다.

프린터 소프트웨어를 사용하여 프린터 큐에 있는 문서의 수와 중요도가 주어졌을 때, 임의 문서가 몇 번째에 인쇄되는지 반환하는 프로그램을 작성하라.

 

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

테스트케이스의 첫번째 줄에는 문서의 개수 n과 인쇄 순서가 궁금한 문서의 현재 위치 m가 주어진다. 위치 m은 0부터 시작한다고 한다.

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

 

 

접근

처음에는 우선순위 큐를 사용하여 문제를 해결하려고 했으나, 맨 첫번째 문서의 우선순위가 나머지 문서보다 낮은 경우 재배치하는 부분에서 어려움을 겪어 그냥 일반 큐로 구현했다. 구현한 방법은 아래와 같다.

 

1. 테스트케이스 수 입력

import sys

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

 

3. n, m, 문서의 중요도를 입력

N, M = map(int, sys.stdin.readline().split())
queue = list(enumerate(map(int, sys.stdin.readline().split())))

문서의 중요도가 같은 문서를 구분하기 위해 문서의 중요도를 입력받을 때는 중요도와 문서의 위치를 함께 저장한다.

 

3. 프린터 큐 구현

프린터 큐는 다음과 같이 구현했다.

• 현재 문서에 접근한다.
• 현재 문서의 중요도와 나머지 문서의 중요도의 최대값을 비교한다.
  • 현재 문서의 중요도가 나머지 문서의 중요도보다 낮으면 : 현재 문서를 다시 큐에 넣는다.
  • 현재 문서의 중요도가 나머지 문서의 중요도보다 높거나 같으면 : 인쇄 순서를 알고자 했던 문서인지 확인한다.
    • 현재 문서가 인쇄 순서를 알려고 했던 문서이면 : 반복을 종료한다.
    • 현재 문서가 인새 순서를 알려고 했던 문서가 아니면 : 인쇄한다.

answer = 1
while queue:
    # 현재 문서 접근
    v = queue.pop(0)
    # 현재 문서의 중요도와 나머지 문서의 중요도의 최대값을 비교
    if queue and v[1] < max(q[1] for q in queue):
        queue.append(v)
    else:
        # 인쇄 순서를 알고자 했던 문서인지 확인
        if M == v[0]:
            break
        else:
            answer += 1
print(answer)

 

전체 코드는 접은글로 적어둔다.

import sys

case = int(sys.stdin.readline())
for _ in range(case):
    N, M = map(int, sys.stdin.readline().split())
    queue = list(enumerate(map(int, sys.stdin.readline().split())))

    answer = 1
    while queue:
        v = queue.pop(0)
        if queue and v[1] < max(q[1] for q in queue):
            queue.append(v)
        else:
            if M == v[0]:
                break
            else:
                answer += 1
    print(answer)

 

 

참고 문서

https://www.acmicpc.net/problem/1966