📌 구해야 하는 정답

1번부터 N번까지 N명의 사람들이 원을 이루며 앉는데, 이 때 순서대로 K번째 사람을 제거합니다.

한 사람이 제거되면 남은 사람들은 이루어진 원을 따라 이 과정을 반복합니다.

이 과정은 N명의 사람이 모두 제거될 때 까지 계속됩니다.

이 순서를 (N,K)-요세푸스 순열이라고 부를 때 이 순열을 구하는 문제입니다.

📌 풀이 하기

1️⃣ K번째 사람 제거하기

K번째 사람을 제거하기 위해서 queue를 이용합니다.

최초 설정

먼저 1부터 N번까지 사람들을 모두 순서대로 queue에 넣어 둡니다.

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

K번째 사람 제외

이 후 K번째 사람을 queue에서 제외합니다.

이를 위해 K-1까지의 사람들은 queue에서 제거함과 동시에 다시 queue에 삽입합니다.

그리고 제거된 사람은 정답 순열을 기록하기 위한 배열에 별도로 기록합니다.

이 과정을 queue가 빌 때 까지 , 즉 모든 사람이 제외 될 때 까지 반복합니다.

while que:
    for _ in range(k-1):
        que.append(que.popleft())
    ans.append(que.popleft())

2️⃣ 형식에 맞게 정답 출력하기

이 문제는 정답을 출력하는 형식이 조금 번거롭습니다.