본문 바로가기
Practice & Study/백준 문제풀이

boj 1158 요세푸스 문제 (python)

문제 中

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, ~

=> 원은 시작과 끝이 없다. 이는 양방향으로 생각할 수 있다. 그러므로 덱을 사용할 수 있다. 

 

(7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

=>

1 2 3 4 5 6 7

4 5 6 7 1 2

7 1 2 4 5  ... 이런식이다.

 

첫번째, 두번째 수를 오른쪽으로 넣어주고, 3번째 수가 가장 왼쪽에 오면 덱의 가장 왼쪽의 값을 pop하면 된다. 

 

from collections import deque
import sys

n, k = sys.stdin.readline().split()
n = int(n)
k = int(k)

deq = deque([i for i in range(1, n+1)])

print('<', end='')

for i in range(n):
    deq.rotate(-k+1)
    print(deq.popleft(), end='')
    if i != n-1:
        print(', ', end='')

print('>')