백준 1158번, deque와 replace

문제 

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

1158번: 요세푸스 문제

 

나의 풀이

from collections import deque

n,k=map(int,input().split())
queue = deque()
for i in range(1, n+1): queue.append(i)
permutation = []

while queue:
    for _ in range(k-1):
        queue.append(queue.popleft())
    permutation.append(queue.popleft())

print(str(permutation).replace('[', '<').replace(']', '>'))

처음에 deque를 사용하지 않아 시간초과가 났었었다.  (deque는 '덱'이라 읽는다.)

deque를 사용 후 시간 초과를 해결 할 수 있었다.

 

deque란 ?

deque는 쉽게 list처럼 요소들을 한 곳에 담아두는 배열이다. 파이썬에서 queue는 First In First Out(FIFO)의 방식으로 작동된다. 덱은 큐이지만 양방향인 queue이다. 양 쪽 방향 모두에서 요소를 추가/제거할 수 있기 때문이다.

List도 있는데 deque를 사용하는 이유는 List보다 deque의 속도가 append/remove/push/pop에 있어 list는 O(n)의 속도, deque는 O(1)의 속도로 더 빠르기 때문이다.

 

replace 함수 (문자열.replace("검색문자","치환 문자",치환 횟수))

위의 풀이에서 list인 permutation을 문자열로 변경하고 replace 함수를 사용하여 '['를 '<'로, ']'를 '>'로 치환해주었다.

이 풀이에서는 list의 []를 바꾸기 위해 사용하였지만 list의 원소들을 치환하기 위해 리스트.replace("검색문자","치환 문자",치환 횟수)로 사용하기도 한다.