[Python] Deque

파이썬에서 Deque를 사용해보자!

deque는 단방향 삽입, 삭제가 가능한 queue와는 달리 양방향 삽입, 삭제가 가능한 자료구조이다. pop(), popleft(), append(), appendleft() 를 통해 양방향 삽입, 삭제가 가능하다.

form collections import deque

queue = deque()

collections 모듈에 있는 deque를 사용하려면 위와 같이 import하여 사용한다!

deque의 함수들을 알아보자!

q = deque() 
q.append(1)   #[1] 오른쪽에 추가
q.appendleft(0)  #[0,1] 왼쪽에 추가
q.popleft() #[1] 왼쪽 삭제
q.pop() #[] 오른쪽 삭제
q.extend([7,8,9]) #[7,8,9] 순서대로 가장 오른쪽에 추가
q.extendleft([2,1,0]) #[0,1,2,7,8,9] 순서대로 가장 왼쪽에 추가
q.insert(3,6) #[0,1,2,6,7,8,9] index 3에 6을 추가
q.remove(6) #[0,1,2,7,8,9] value의 첫번째 6을 제거
q.reverse() #[9,8,7,2,1,0] deque의 순서를 뒤집기
q.rotate(1) #[0,9,8,7,2,1] 1만큼 오른쪽으로 rotation.n이 음수이면 왼쪽으로 rotation

백준 1158 요세푸스 문제

딱 문제를 읽고 원형 연결 리스트를 떠올렸는데 deque로 비슷하게 풀 수 있을 것 같았다! K-1만큼 왼쪽으로 rotation 후에 popleft를 통해 정답 순열에 추가하면 요세푸스 순열이 완성된다~

N,K = map(int, input().split())

from collections import deque

one = deque(i for i in range(1,N+1))

ans=[]

num=1
print('<', end='')
while(one) :
    one.rotate(-(K-1))
    print(one.popleft(), end='')
    if not one : break
    print(', ', end='')
print('>', end='')