[Baekjoon 11866 / python / 실버5] 요세푸스 문제 0

from collections import deque

n, k = map(int, input().split())

result = []

human = deque()

for i in range(n): # 1 ~ n을 queue에 담는다

    human.append(i + 1)

while human:  # 사람이 다 죽으면 반복 종료

    for _ in range(k - 1):

        human.append(human.popleft()) # k번째 사람을 죽여야 하니, k - 1번 이동하여 죽일 사람 선택

    result.append(str(human.popleft())) # 선택된 사람 죽여서 결과 리스트에 순서대로 담기

print('<', end='')

print(', '.join(result), end='')

print('>')

 

큐를 사용하는 문제이다. 난 스택과 큐의 장점을 합친 파이썬의 deque를 import하여 사용했다.

 

원형으로 둘러앉은 n명의 사람이 있을 때, k번째에 있는 사람을 계속 죽여 모두가 죽을때까지 진행한다.

다 죽인 후엔, 어떤 순서로 죽였는지 출력하면 된다.

 

human.append(human.popleft()) 를 하게 되면 가장 왼쪽의 값이 가장 오른쪽으로 들어가게 되는데, 이것이 다음 사람을 선택하는 과정과 동일하다. 즉, 죽일 사람을 큐의 가장 왼쪽에 오게 하기 위해 이 작업을 하는 것이다.

가장 왼쪽의 사람을 k-1번 오른쪽으로 옮기게 되면 죽여야 할 k번째의 사람이 가장 왼쪽에 오게 된다.

이때 popleft()로 왼쪽 사람을 죽여서 result에 담는 것이다.

 

편의상 왼쪽, 오른쪽이라고 표현했지만 원으로 둘러앉아 있다고 생각하는 것이 맞긴 하다.