import time
import sys
from collections import deque
import heapq
input = sys.stdin.readline
start_time = time.time()
# code start
inputs = list(map(int, input().split()))
people = [x+1 for x in range(inputs[0])]
answer = []
n = inputs[1]
for _ in range(inputs[0]) :
answer.append(people[n%len(people)-1])
people.remove(people[n%len(people)-1])
people = people[n % len(people)-1:] + people[: people[n%len(people)]-1]
print(answer)
# code finish
end_time = time.time()
print(f'실행시간 {end_time - start_time}')
결과
시간초과
결과는 원하는 대로 나옴
원인
- 파이썬 리스트는 동적 배열로 구현되어있어서 사실상 배열이다. 그래서 삭제, 삽입에는 O(N)의 시간복잡도를 가진다.
- 그래서 people.remove 저부분이 문제가 되는 것.
해결방법
- deque
- 덱은 양쪽 긑에서 항목을 추가하거나 삭제하는 연산을 O(1)의 시간복잡도로 수행할 수 있게 해주는 양방향 큐이다.
- 그래서 순환하는 큐가 필요하거나, 앞, 뒤, 양쪽에서의 추가 / 삭제가 자주 일어나는 경우에 매우 유용하다.
import time
import sys
from collections import deque
import heapq
input = sys.stdin.readline
start_time = time.time()
# code start
N,K = map(int, input().split())
people = deque(range(1, N+1))
answer = []
while people :
people.rotate(-K+1)
answer.append(people.popleft())
print(answer)
# code finish
end_time = time.time()
print(f'실행시간 {end_time - start_time}')
참조
deque의 rotate
- deque의 모든 요소를 n만큼 오른쪽으로 회전시킨다.
- n이 음수면 왼쪽으로 회전시킨다.
- 회전이란 모든 요소를 n위치만큼 이동시키는 것을 말하며, 덱을 넘어서면 반대쪽 끝으로 넘어서게 된다.
- 요세푸스에는 이게 직빵이다.
결과물 포메팅
print('<'+ ','.join(map(str, answer))+ '>')