요세푸스 문제(python)

문제 설명

1부터 N까지의 사람들이 원으로 앉아있다고 하자. K번째 사람들을 제거하는 방법을 이용해서 모든 사람을 제거한다. 이때 제거된 사람들의 순서를 구하시오.

문제 풀이

첫 번째 접근

처음에는 나누기로 푸는 줄 알았다. K번째 사람이니까. 근데, 사람들은 원으로 앉아있고 한 사람이 제거 될 때마다 사람들이 앞으로 당겨진다. 그러면 어떻게 해야 하는가> 정답은 문제 분류에 있었다.

두 번째 접근

문제 분류는 큐로 되어 있다. 즉, k-1까지 사람을 뽑아 뒤로 붙이고 K번째 사람이 앞에 나오면 제거한다. 이 방법을 큐에 사람이 한 명 남을 때까지 계속한다(반복문의 조건을 0으로 두면 빈 공간에서 pop을 해야 하는 경우가 생기기 때문이다). 이걸 리스트에 담아 가지고 문제 출력 조건처럼 문장을 만들어 준 뒤 출력하면 된다.

코드

Python

from sys import stdin
from collections import deque

N, K = map(int, stdin.readline().strip().split(" "))
answer_list = []
queue = deque([])
answer = '<'

for i in range(1, N+1):
    queue.append(str(i))

while len(queue) != 0:
    for j in range(K-1):
        queue.append(queue.popleft())

    answer_list.append(queue.popleft())

answer_list.append(queue.popleft())

answer += ', '.join(answer_list)
answer += '>'

print(answer)