[백준] 11866번 요세푸스 문제 0 - Python

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1

7 3

예제 출력 1

<3, 6, 2, 7, 5, 1, 4>

예제 1 풀이

1, 2, 3, 4, 5, 6, 7
-> 3
1, 2, 4, 5, 6, 7
-> 6
1, 2, 4, 5, 7
-> 2
1, 4, 5, 7
-> 7
1, 4, 5
-> 5
1, 4
-> 1
4
-> 4

정답 1

본래와 같으면 예제 1 풀이와 같은 방식으로 풀려고 시도를 했었다. 하지만, index를 구하여 하는 방법은 생각보다 까다로웠고 다른 방법을 찾다보니 deque를 통해서 순서를 바꾸어가면서 하는 방법이 있었다. 방법은 다음과 같다.
1, 2, 3, 4, 5, 6, 7
<3> / 4, 5, 6, 7, 1, 2
<3, 6> / 7, 1, 2, 4, 5
<3, 6, 2> / 4, 5, 7, 1
<3, 6, 2, 7> / 1, 4, 5
<3, 6, 2, 7, 5> / 1, 4
<3, 6, 2, 7, 5, 1> / 4
<3, 6, 2, 7, 5, 1, 4>

from collections import deque
n, k = map(int, input().split())
deque = deque([])

for i in range(1, n + 1):
    deque.append(i) # deque에 1 ~ n까지 추가

print('<', end='')
while deque: # deque가 비어있다면 False, 요소가 있다면 True를 반환한다
    for i in range(k - 1): # deque에서 k번전까지 0번째 요소를 뒤에 추가하고 삭제한다.
        deque.append(deque[0])
        deque.popleft()
    print(deque.popleft(), end='')
    if deque:
        print(', ', end='')
print('>')