백준_python 1158번 요세푸스 문제 (deque, 수학, 시간복잡도)

<문제 링크>

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

 

 

<정답 코드>

 sol1 ) deque을 이용한 풀이

from collections import deque
 
n, k = map(int, input().split())
q1 = deque([i for i in range(1,n+1)])
answer = []
 
for _ in range(n):
    for _ in range(k-1):
        q1.append(q1.popleft())
    answer.append(q1.popleft())
 
print('<',end='')
print(*answer, sep=', ', end='>')

 

deque를 이용한 직관적 풀이

그러나 시간복잡도가 O(N*k)로, k 크기 증가하면 비효율적

 

 

 sol2 ) 요세푸스 문제 수학적 풀이

n, k = map(int, input().split())
people = list(range(1, n + 1))
answer = []
index = 0
 
while people:
    index = (index + k - 1) % len(people)
    answer.append(people.pop(index))
 
print('<', end='')
print(*answer, sep=', ', end='>')

 

deque이 아니라 리스트 사용

인덱스를 계산해서 배열 값에 직접 접근

시간복잡도 O(N)으로 개선