[Python] 백준 1158번: 요세푸스 문제

풀이 전략은 다음과 같습니다.

1번에서 N번의 사람들이 모두 제거될 때까지 반복하며 요세푸스 순열을 구해야 하는데요,
1번에서 N번까지 순회한 다음, 다시 1번으로 돌아가는 과정을 어떻게 구현하면 좋을까요?

큐를 이용하면 N번까지 순회한 후 다시 1번으로 돌아가는 과정을 편리하게 구현할 수 있습니다.

큐에 1 ~ N을 차례로 enqueue한 다음
큐의 front를 dequeue하고 front를 다시 enqueue한다면

dequeue된 item이 다시 큐의 rear로 들어가며 끊임없이 돌고 도는 순회가 가능하겠죠?
이 방법으로 모든 사람이 제거될 때까지 순회하며 반복할 수 있습니다.

만약 K번째 사람이라면 요세푸스 순열에 추가하고,
K번째 사람이 아니라면 다시 rear로 enqueue해주어 모든 사람이 제거될 때까지 반복하면 됩니다.

from collections import deque
N, K = map(int, input().split())
ans = '<'
deq = deque(p for p in range(1, N+1)) # 덱에 1~N 저장

while True:
    if len(deq) == 0:
        print(ans[:-2] + '>')
        break
    for i in range(K):
        item = deq.popleft()
        if i != K-1: # K번째 사람이 아니면 다시 enqueue
            deq.append(item)
        else: # K번째 사람이면 ans에 추가
            ans += str(item) + ', '

큐를 이용하여 순회하는 방식을 떠올리는 것이 중요한 문제였던 것으로 보입니다.