[Python] 백준 / 요세푸스 문제 / 1158번 / que

문제

요세푸스 문제 링크

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

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 ≤ 5,000)

7 3

출력

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

접근 방식

1. n 크기의 리스트를 만든다

2. 리스트의 인덱스를 가리키는 포인터를 만들어 k만큼 더해간다

3. 포인터를 리스트 크기로 나눠 나머지를 포인트에 다시 할당한다

4. 포인터가 가리키는 값을 현재 리스트에서 삭제하고 정답 리스트에 넣는다

5. 포인터가 가리키던 값을 지웠기 때문에 포인터를 낮추고 리스트 크기도 낮춘다

코드

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

# 1부터 n까지 list
yo_li = list(range(1,n+1))
answer = []

# yo_li의 값을 가리킬 인덱스 (yo_li의 마지막 인덱스로 초기화)
pointer = n - 1

# yo_li의 크기
d = n

while yo_li :
    # pointer에 k 만큼 더한 값의 나머지를 pointer에 넣는다
    pointer += k
    pointer %= d

    # pointer가 가리키는 값을 yo_li에서 지우면서 answer 리스트에 넣는다 (나중에 join하기 위해 str값으로 변환)
    answer.append(str(yo_li.pop(pointer)))

    # 가리키던 값이 지워졌으므로 pointer를 한칸 왼쪽으로 옮기고 d 값도 줄인다
    pointer -= 1
    d -= 1

print('<',end='')
print(', '.join(answer), end='>')