https://www.acmicpc.net/problem/1158
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
문제
N명의 사람이 원을 이루면서 앉아있는 상태에서, 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 또 K번째 사람을 제거한다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다.
입력
N: 원을 이루는 사람의 수
K: 제거되는 사람의 순서
출력
요세푸스 순열
제약
1 <= K <= N <= 5,000
예제
7명의 사람이 원을 이루면서 앉아있는 상태에서, 7명의 사람이 모두 제거될 때까지 3번째 사람을 계속 제거해야 한다.
그림에서 노란색은 루프마다 제거되는 사람의 위치를 표시한 것이다.
1) N = [1, 2, 3, 4, 5, 6, 7] -> 3번째인 3이 제거된다.
2) N = [1, 2, 4, 5, 6, 7] -> 3이 제거된 후, 3번째가 6이므로, 6이 제거된다.
3) N = [1, 2, 4, 5, 7] -> 6이 제거된 후, 3번째가 2이므로, 2가 제거된다.
...
위와 같은 과정은 7명이 모두 제거될 때까지 반복되고, 결과적으로 요세푸스 순열이 <3, 6, 2, 7, 5, 1, 4>로 출력된다.
코드
"""
Input: N(인원 수), K(제거하는 사람 순서)
Output: 요세푸스 순열(원에서 사람들이 제거되는 순서)
Constraints: 1 <= K <= N <= 5,000
시간 복잡도
while 루프 -> O(n)
for 루프 -> O(k-1)
-> 총 연산 횟수 n*(k-1) -> O(n*k) -> O(N)
공간 복잡도: queue, answer의 크기 = n -> O(N)
"""
from collections import deque
n, k = map(int, input().split())
queue = deque(range(1, n + 1))
answer = []
while queue: # queue에 요소가 남아있는 동안 계속된다. O(n)
for _ in range(k-1): # O(k-1)
queue.append(queue.popleft())
answer.append(queue.popleft())
# 총 연산 횟수 n*(k-1) -> O(n*k) -> O(N)
print(str(answer).replace('[', '<').replace(']', '>'))