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

문제

 

 

풀이 과정의 고민

• 출력할 문서의 위치를 어떻게 이동시킬지 고민했어요. 방법은 다양할 수 있는데, 출력 위치가 0번 인덱스로 고정되어 있기 때문에 원형 큐처럼 인덱스를 따라 돌게 만들기로 했어요. enumerate를 통해 인덱스와 중요도를 튜플로 묶으면 생각하기 편하긴 하지만 자료의 수가 늘어날수록 성능에 영향을 미치게 되어 정수 하나의 인덱스로 관리하는 게 더 낫다고 판단했어요.
• 파이썬에서 제공하는 기본 리스트 자료구조의 경우 내부적으로 더블 링크드 리스트이지만 사용 시 스택처럼 작동하기 때문에 pop(0)을 사용하는 것을 피하려고 했어요. 인덱스 1번부터 요소가 존재한다면 전부 시프팅이 일어나기 때문이에요. 그래서 대안으로 생각한 것은 주어진 자료구조를 reverse 해 pop(0)가 아닌 pop()으로 출력하는 구조로 구현하거나 Deque 자료구조를 사용하는 거예요. 풀이에서는 Deque을 사용했어요. Deque을 사용하면 O(1)로 0번째 인덱스를 제거 가능하기 때문이에요.
• Java에서 else 사용을 기피하는 습관이 생겨 else를 사용하지 않았었는데 알고리즘 가독성 측면에서 오히려 else가 있는 것이 보기 좋은 것 같아요.

 

 

풀이

from sys import stdin
from collections import deque

input = stdin.readline

T = int(input())
for _ in range(T):
    N, target = map(int, input().split())
    N_list = deque(list(map(int, input().split())))
    order = 1
    while True:
        if N_list[0] == max(N_list):
            if target == 0:
                print(order)
                break
            else:
                N_list.popleft()
                order += 1
                target = (target + len(N_list) - 1) % len(N_list)
        else:
            target = (target + len(N_list) - 1) % len(N_list)
            N_list.append(N_list.popleft())

 

 

풀이할 때 생긴 에러

• 출력 순서를 order라는 int 변수로 관리했는데 +1 하는 시점을 잘못 설정했어요. 출력했을 경우에는 order가 1이 증가하면 안 되는데 인덴트를 잘못 설정해서 while 구문이 돌 때마다 order가 증가하는 문제가 있었어요. else를 구분함으로써 해결했어요.
• target은 출력할 문서의 위치를 의미하는데 위치를 조정하는 로직을 잘못 작성했어요.
  

  # 변경 전
  target = (target + N - 1) % N
  
  # 변경 후
  target = (target + len(N_list) - 1) % len(N_list)​

  숫자 N은 최초의 리스트 길이이고 출력 때마다 리스트의 길이가 짧아지는데 그걸 반영하지 않아서 문제가 생겼어요. 백준 알고리즘 문제를 풀 때 다른 언어와 다르게 파이썬은 배열의 길이를 미리 설정하지 않아도 되기 때문에 자료 개수라는 변수를 무의미하게 받는 경우가 많아요. 백준은 여러 언어를 커버하는 문제를 출제하기 때문이에요. 그래서 저 변수를 어떻게든(?) 사용하려다 보니 오히려 실수하게 되었어요.

다른 풀이

test_case = int(input())
for _ in range(test_case):
    n, m = list(map(int, input().split(' ')))
    queue = list(map(int, input().split(' ')))
    queue = [(i, idx) for idx, i in enumerate(queue)]
    count = 0
    while True:
        if queue[0][0] == max(queue, key=lambda x: x[0])[0]:
            count += 1
            if queue[0][1] == m: 
                print(count)
                break 
            else:
                queue.pop(0)
        else:
            queue.append(queue.pop(0))

위에서 언급했듯이 enumerate를 통해 초기 인덱스와 값을 함께 가지는 배열을 생성하는 방법이에요. 로직은 생각하기 조금 더 편한 방식이에요. 다만, 리스트의 요소를 전부 다시 갱신해야 한다는 점, 그리고 pop(0)를 통해 값을 꺼내온다는 점이 아쉬워요. 물론 문제에서 주어지는 숫자의 범위가 작기 때문에 성능상에 큰 차이를 내지는 않는다고 생각해요.

 

 

문제 출처

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