[백준] 1158번 (python 파이썬)

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

1158번: 요세푸스 문제

 

from collections import deque
n, k = map(int, input().split())
queue = deque(range(1, n+1))
result = []
for _ in range(n):
  for _ in range(k-1):
    queue.append(queue.popleft())    
  else:
    result.append(queue.popleft())
print(str(result).replace("[", "<").replace("]", ">"))

 

큐 자료구조의 앞 부분을 제거해서 뒷 부분에 추가하면 회전이 된다.

하물며, deque 객체는 안의 요소들을 회전해주는 메서드를 제공한다.

 

deque.rotate(n=1)

deque를 n 단계 오른쪽으로 회전합니다. n이 음수이면, 왼쪽으로 회전합니다.

 

직접 제거/추가를 통해 회전하는 것과 rotate()메서드를 통해 회전하는 것을 비교해보았다.

최악의 경우를 제시했을 때의 시간을 본다.

from collections import deque
import time
n, k = 5000, 5000
queue = deque(range(1, n+1))

start = time.time()
for _ in range(k):
  queue.append(queue.popleft())  
end = time.time()
a = end-start

start = time.time()
for _ in range(k):
  queue.rotate()  
end = time.time()
b = end-start

print("a" if a>=b else "b")

 

출력 결과는 a이다.

즉, 위의 문제풀이엔 rotate()메서드를 이용하는 것이 더 빠르다.