[백준알고리즘] 1966번: 프린터 큐 -Python

[백준알고리즘] 1966번: 프린터 큐 -Python

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

1966번: 프린터 큐

 

이전에 푼 2164번 문제처럼 큐의 문제를 덱을 사용해서 풀 것이다.

 

여기서는 Priority Queue를 사용해도 되나 그냥 여러 리스트들을 이용해서 풀었다.

Priority Queue를 사용해서 푼다면 정렬 기준은 2가지가 될 것이다.

1. 우선 순위가 높아야 함

2. 우선 순위가 같다면 앞에 있는 게 먼저 실행됨 (이건 뒤로 이동한 문서도 고려해주어야 한다.)

 

 

 

하지만 처음에 말했듯이 우선순위 큐를 사용하지 않고 풀었다.

 

여기서 리스트를 3개, 덱을 1개 사용했다.

하지만 리스트에서 result는 사실 없어도 되고 (바로 M에 일치하는 인덱스의 값이 나오면 출력하도록 하면 된다) 범위도 세세하게 설정해주지 않았다. (잉여 인덱스가 있다)

이건 뭐 여기서는 중요한게 아니니까 일단 넘어가고 설명을 해보겠다.

 

 

각 테스트 케이스마다 입력하는 우선순위는 input에다가 저장을 하고 각 input에 입력될 때마다 해당 값을 인덱스로 하는 exist배열을 +1씩 시켜준다.

예를 들어서 3 7 5이 입력된다고 했을 때, 0으로 초기화되어있던 exist리스트의 exist[3] = 1, exist[7] = 1, exist[5] = 1 순서대로 정해진다는 것이다.

 

이 값을 exist리스트에 +1씩 시켜주는 이유는 현재 그 값의 개수를 파악하기 위해서이다.

 

값의 개수를 파악하는 이유는 간단하다. 현재 큐에서 맨 앞의 값이 3일 때 exist에서 인덱스가 3보다 큰 값이 있다면 그건 큐에서 3보다 높은 값이 존재한다는 말과 같은 뜻이기 때문이다. 따라서 위의 예시에서는 exist[5]에서 0보다 크기 때문에 큐 뒤에는 5가 존재한다는 뜻이다.

 

그래서 3을 맨 뒤로 보내서 7 5 3이 되었다고 하자. 그러면 exist[7]보다 높은 인덱스에서 0보다 큰 값을 갖는 인덱스는 없다. 그 말은 현재 큐에서 7 뒤에는 7보다 큰 값이 없다는 것이기 때문에 7이 첫 번째로 출력이 된다는 것이다.

 

마찬가지로 반복해주면 된다.

 

 

 

문제를 이 아이디어를 가지고 풀었다고 생각하면 된다. 그런데 같은 값들을 처리해주기 어려워지기 때문에 queue로 사용한 deque에는 index를 넣어주었다.

 

즉 처음에 3 7 5가 입력되었을 때 input에 저장되어있는 것이고, queue에는 0 1 2가 저장되어 있다는 것이다.

 

따라서 다시 정리하자면 queue에서 index를 뽑아내고, index를 이용해서 input에서 value를 뽑아내고,  그 value를 이용해서 해당 value보다 큰 값이 있는지 검사를 수행한 것이다. 해당 value보다 큰 값이 없다면 해당 result[index]에 몇 번째 출력되는지 저장하면 된다.

 

 

설명이 머리아플 수 있지만 코드를 보면 이해가 될 듯 하다. 위의 아이디어로 푼 코드는 아래에 있다.

 

import sys
from collections import deque

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

for t in range(test_case):
    N, M = map(int, sys.stdin.readline().split())

    exist = [0 for _ in range(101)]
    result = [0 for _ in range(100)]
    input = list(map(int, sys.stdin.readline().split()))
    queue = deque()

    for i in range(N):
        queue.append(i)
        exist[input[i]] += 1

    cnt = 1
    while queue:
        idx = queue.popleft()
        value = input[idx]

        flag = True
        for i in range(value + 1, 10):
            if exist[i] > 0:
                flag = False
                break

        if flag:
            exist[value] -= 1
            result[idx] = cnt
            cnt += 1
        else:
            queue.append(idx)

    print(result[M])

 

테스트 케이스는 이 문제가 나왔던 홈페이지에 많이 있었다.

http://www.csc.kth.se/contest/nwerc/2006/

위의 링크에서 test case를 다운받고 그중에서 printerqueue를 보면 된다.

 

다른 좋은 풀이들도 많이 있었으니 많이 보는 것이 좋을 것 같다.

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다