Solved.ac Class [2]

실버 4 등급 : 요세푸스 문제 0

문제 설명

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

예제 입출력

input
7 3
output
<3, 6, 2, 7, 5, 1, 4>

문제 접근 방식

문제를 잘 이해했는지가 중요하다.

  1. K번째 사람을 뺀다
  2. K+1 번째 사람 부터 다시 시작한다.

위 예제를 사용한다면

1 2 `3` 4 5 6 7
4 5 `6` 7 1 2
7 1 `2` 4 5
4 5 `7` 1
1 4 `5`
`1` `4`

이런식으로 사람들이 줄어든다고 볼 수 있습니다.

처음에는 for문과 빈 리스트를 활용해서 하나씩 append한 후 리스트 배열을 다시 맞춰줬습니다. 하지만 틀렸고.. 그리고 <>이 표시를 꼭 output 과 같이 붙여 줘야합니다. 그래서 생각한 것이 deque입니다.

from collections import deque
import sys
n, k = map(int, sys.stdin.readline().split())

queue = deque(x for x in range(1,n+1)) # 1번부터 N번까지
answer = []

while queue:
    for i in range(k-1): # 1번 부터시작했기 때문에 k-1번째 까지 뒤로 보내줍니다.
        queue.append(queue.popleft())
    answer.append(queue.popleft()) # 맨 앞에 오게된 k번째를 answer에 추가합니다.

# output를 출력하는 과정입니다. end=''를 통해 이어붙여 줍니다.
print("<",end='')
for i in range(len(answer)-1):  # 마지막 원소 뒤에 ,를 붙이면 안되기 때문에 그 전까지만 출력후 따로 anwer[-1]째를 출력하도록 합니다.
    print("%d, "%answer[i], end='')
print(answer[-1], end='')
print(">")