백준 알고리즘 1966번: 프린터 큐 (Python)

문제 정보

---

1966번: 프린터 큐

 

 

핵심

---

이 문제를 풀수 있는 많은 풀이들이 존재할 것인데, 나는 deque 를 이용하여 풀이를 진행하였다.

priority 라는 배열을 만들고, 해당 배열에서 인덱스는 중요도를 뜻하며 배열의 요소는 해당 중요도를 가지는 문서의 개수를 의미한다.

 

deque에서의 popleft() 연산을 통하여 큐에서 문서를 꺼내고, priority 배열을 확인하여 꺼낸 문서의 중요도보다 높은 문서가 큐에 존재하는지 여부를 판단하며, 있다면 append() 연산으로 다시 큐에 문서를 넣고 없다면 count를 올려주면 된다.

 

풀이

---

import sys
from collections import deque

n = int(sys.stdin.readline().strip())
for _ in range(n):
    N, M = map(int, sys.stdin.readline().split())
    L = map(int, sys.stdin.readline().split())
    D = deque()
    priority = [0 for _ in range(10)]
    for i in L:
        D.append(i)
        priority[i] += 1

    count = 0
    while True:
        relocation = False
        item = D.popleft()
        M -= 1

        for p in range(item+1, 10):
            if priority[p] > 0:
                relocation = True
                break
                
        if relocation:
            D.append(item)
            if M == -1:
                M = len(D)-1
        else:
            if M == -1:
                count += 1
                print(count)
                break
            else:
                priority[item] -= 1
                count += 1

 

꺼낸 문서보다 중요도가 높은 문서가 존재하면 relocation (꺼낸 문서를 다시 큐에 집어넣는 작업) 을 실시하고

M은 1씩 빼가는 과정을 통하여 중요도를 파악할 문서의 위치를 알 수 있게 해 주었다

 

고찰

---

살짝 시간이 많이 걸렸던 것 같다

처음에는 deque를 사용하지 않고 공식같은 것을 탐구하여 문제를 풀이하려 하였지만 변수가 너무 많았다

처리해 주어야 할 것들이 많아서 조금 시간이 많이 소요되지 않았나 싶다

 

또한 이 문제를 리스트로 풀 수도 있었다

import sys
x = int(sys.stdin.readline())
for i in range(x):
    answer = 0
    cnt = 0
    n ,m = list(map(int,sys.stdin.readline().split()))
    lst = list(map(int,sys.stdin.readline().split()))
    while(lst[m] != 0):
        max_num = max(lst)
        while 1 :
            if lst[cnt] == max_num:
                lst[cnt] = 0
                break
            else:
                cnt = (cnt + 1) % n
        answer += 1
    print(answer)

https://www.acmicpc.net/source/54836946

이분의 풀이를 보면, 리스트에 존재하는 최대값을 구하고, 최대 값을 찾아가며 내용을 0으로 바꾼다.

나는 pop에만 집중하고 있었는데 이렇게도 접근할 수 있구나 생각하였다

 

참조

---

GitHub - dduneon/CodingTestPy