[BOJ][Python] 1158 요세푸스 문제

[문제]

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

1158번: 요세푸스 문제

 

[코드]

첫 번째 풀이: k번째 수까지 반복문으로 pop, append 반복 >> 시간복잡도가 높아짐

#S4_1158 요세푸스 문제.py

from collections import deque as dq

#입력
n, k = map(int,input().split())

arr = [i for i in range(1,n+1)]
q = dq(arr)

answer = []
while True:
    if len(q) == 0:
        break
    for i in range(k-1):
        q.append(q.popleft())
    answer.append(str(q.popleft()))

#출력
print("<"+", ".join(answer)+">")

 

두 번째 풀이: while 부분의 코드에서 for 문을 전부 돌지 않는 점화식을 세운다. 

#S4_1158 요세푸스 문제.py

n, k = map(int,input().split())
arr = [i for i in range(1,n+1)]
answer = []
index = 0

while arr:
    index = (index + k -1) % len(arr)
    answer.append(str(arr.pop(index)))
    
#출력
print("<"+", ".join(answer)+">")

 

시간 차이 확인 가능