[ BAEKJOON ] No. 11866 요세푸스 문제 0

문제 )

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

11866번: 요세푸스 문제 0

 

[ 풀이 ]

1. (k-1)번째 까지의 수는 queue에다가 append해준다 
2. k번째 수는 pop해서 queue에서 없애주고 result 에 넣어주는 것을 
3. queue안의 원소가 하나 남을 때 까지 반복 
4. queue안의 원소가 하나일때 마지막 하나 남은 원소도 result에 넣어준다 

 

Ex )

(7 , 3) 요세푸스 순열의 경우  →  queue= [ 1, 2, 3, 4, 5, 6, 7 ]

순서	제거되는 수	queue	result
1)	3	[ 4, 5, 6, 7, 1, 2 ]	[3]
2)	6	[ 7, 1, 2, 4, 5 ]	[3, 6 ]
3)	2	[4, 5, 7, 1 ]	[3, 6, 2]
4)	7	[1, 4, 5]	[3, 6, 2, 7 ]
5)	5	[1, 4 ]	[3, 6, 2, 7 ]
6)	1	[4]	[3, 6, 2, 7, 1]
7)	- (append해줌)	[4]	[3, 6, 2, 7, 1, 4]

 

 

- python code

from collections import deque

def Jose(arr, k):
    result=[]
    while len(arr)!=1:
        for i in range(k-1):
            arr.append(arr.popleft())
        result.append(arr.popleft())
    # 마지막 1개 남았을 때
    result.append(arr[0])
    print("<"+", ".join(map(str,result))+'>')


N,K=map(int, input().split())
queue=deque(i for i in range(1,N+1))
Jose(queue,K)