요세푸스 문제 0

노누리·2022년 6월 28일

문제

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

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

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

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1

7 3

예제 출력 1

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

문제 풀이

n,k=map(int,input().split())
idx=k
queue=[i for i in range(1,n+1)]
answer=[]

while len(queue)!=0:
    idx=(idx-1)%len(queue)
    answer.append(queue[idx])
    del queue[idx]
    idx+=k

print('<',end='')
for i in range(len(answer)):
    if i==len(answer)-1:
        print(answer[i],end='')
    else:
        print(answer[i],end=', ')
print('>')

k번째 숫자를 제외하는 방식을 숫자가 없어질때까지 반복하면 되는 간단한 로직이다.

하지만 이때, k는 매번 0번째부터 시작하는 것이 아니라 이전에 삭제했던 숫자의 위치에서 k번째를 찾는것으로 매번 갱신된다.

리스트의 길이를 넘어가는 인덱스를 처리하는 방법에는 % 나머지를 이용하는 방식이 있다.

매번 인덱스를 계산할때 k를 더해주면서 queue의 길이만큼 나머지를 구해주면 다음 인덱스 위치를 계산할 수 있다.

하지만 이때, k번째 위치의 리스트를 삭제하기 때문에 (k-1)를 더해주어야 정확하다.

그리고 출력 방식을 <숫자, 숫자, ...> 형식으로 해주어야 해서 for문과 end를 이용하여 출력 형식을 맞췄다.

리스트를 이용하여 del로 삭제하는 방식을 사용했지만 queue를 이용하여 구현할 수도 있다.

queue를 이용한 풀이

from collections import deque
n,k=map(int,input().split())
queue=deque([i for i in range(1,n+1)])

print('<',end='')
while len(queue)!=0:
    for _ in range(k-1):
        queue.append(queue.popleft())
    if len(queue)!=1:
        print(queue.popleft(),end=', ')
    else:
        print(queue.popleft(),end='>')