[파이썬] 백준 BOJ 1966번 프린터 큐

강준호·2023년 3월 14일
0

초고

  • 딕셔너리를 이용해 {인덱스: 중요도} 로 풀려고 시도했다. => 중요도가 중복되는 것들이 많아서 key value 로 풀기 어려움.

  • queue 를 이용하기로 하자

queue를 이용한 풀이

import sys

t = int(sys.stdin.readline().strip()) # 테스트케이스의 수
for i in range(t):
    n, m = map(int, sys.stdin.readline().split())
    imp = list(map(int,sys.stdin.readline().strip().split())) #queue
    cnt = 1
    while True:
        if m !=0:
            if imp[0] == max(imp):
                cnt+=1
            else :
                imp.append(imp[0])
            del imp[0]
            m-=1
        else:
            if imp[0] == max(imp):
                print(cnt)
                break
            else:
                imp.append(imp[0])
                del imp[0]
                m = len(imp)-1
  • 큐를 이용해 풀이해봤는데 정답은 맞았지만
    뭔가 또 중복 코드가 많고 지저분하다.

  • 타 풀이들 보다 성능도 떨어지는 느낌ㅜ

개선된 코드

import sys
from collections import deque

t = int(sys.stdin.readline().strip()) 
for i in range(t):
    n, m = map(int, sys.stdin.readline().split())
    imp = deque(map(int,sys.stdin.readline().strip().split())) 
    cnt = 0
    while imp:
        if imp[0] == max(imp):
            cnt += 1
            if m == 0:
                print(cnt)
                break
            else:
                imp.popleft()
                m -= 1
        else:
            imp.rotate(-1) # 맨뒤로가
            m = (m - 1) % len(imp) 

수정사항

  • while imp: 로 pop할때 imp가 비어있는지 걱정하지 않아도 된다.

  • 리스트로 만든 큐에서 계속 del[0]을 사용하기보다
    deque 을 채택해 popleft()로 앞에서도 pop할 수 있게 만든다.

=> 양끝 엘리먼트(element) 삽입, 제거를 할때
리스트(list)는 O(n)이 소요 but 데크(deque)는 O(1)로 매우 빠름

  • 덱의 회전메소드 rotate()를 사용해 내가 수작업으로 del[0] 후에 append(imp[0])을 하지않아도된다.

논점) 위 코드에서 m = (m - 1) % len(imp) 이 왜 m = len(imp) -1 이 되면 결과가 달라질까?

m= len(imp) - 1 이면 회전 후 m이 len(imp)와 같아 범위를 벗어난다.
그래서 안전하게 (m-1) % len(imp) 을 사용하는것!

이해가 되지 않는다면 예시를 보자

Queue [2, 1, 4, 3]라고 하고

queue[2]에 있는 우선순위 4를 위치를 찾는다고 하자

한 회전 후에 Queue는 [1, 4, 3, 2].

우선 순위가 4인 문서가 이제 queue[1]에 있다. 
=> m 값을 하나 당겨야해! 


만약 회전 전 m이 len(imp) - 1이면(여기선 3) 회전 후 m은 len(imp)와 같을 것이다.
=> rotate 기 때문에 큐의 len은 달라지지 않거든. 

index 초과 에러 발생!

한편 (m - 1) % len(imp) 에서 m-1 < len(imp)이다. 항상!

따라서 모듈러 연산값은 큐를 넘지 않으면서 항상 m-1 

참고) deque.rotate(num): 데크를 num만큼 회전한다

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

deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4]) 양수면 맨앞으로가

deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5]) 음수면 맨뒤로가


# 참고 출처: https://chaewonkong.github.io/posts/python-deque.html

0개의 댓글