[python] 백준 11866번 : 요세푸스 문제 0

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

 

예를 들어, n = 7, k = 3인 경우를 생각해봅시다:

1. 초기 배열: [1, 2, 3, 4, 5, 6, 7]
2. 3번째 사람(3)이 제거됩니다: [1, 2, 4, 5, 6, 7]
3. 다음 3번째 사람(6)이 제거됩니다: [1, 2, 4, 5, 7]
4. 계속해서 3번째 사람(2)이 제거됩니다: [1, 4, 5, 7]
5. 반복해서 3번째 사람(7)이 제거됩니다: [1, 4, 5]
6. 또 다시 3번째 사람(5)이 제거됩니다: [1, 4]
7. 마지막으로 3번째 사람(1)이 제거됩니다: [4]
8. 최후에 남는 사람은 4입니다.

앞에 있는 인덱스를 맨뒤로 옮겨야 하므로 리스트로 풀게되면 시간 복잡도 많이 증가하므로 queue로 푸는게 효율적이다. k의 갯수만큼 앞에서 빼서 뒤로 옮긴다음 맨 앞에있는 숫자를 제거하면 원하는 값을 구할 수 있다. deque.popleft() 와 dequq.append() 로 rotate 를 해주면 된다.

import collections

n , k = map(int,input().split())
arr = collections.deque( [i for i in range(1,n+1)])
result = []
index = 0
for i in range(n):
    for _ in range(k-1):
        arr.append(arr.popleft())
    result.append(arr.popleft())

resultstr = ', '.join(map(str,result))
print(f'<{resultstr}>')