[구현/수학] 백준 11866 요세푸스 문제 0 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11866번: 요세푸스 문제 0

 

 

 

2. 문제 풀이

 요세푸스 순열은 N개로 이루어진 원에서 K마다 제거되는 숫자를 모아둔 걸 뜻합니다. 주어지는 N과 K에 따라 형성되는 요세푸스 순열을 출력해야 하는 문제입니다.

 

2022.02.10 - [Algorithm] - [Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

[Algorithm] 큐(Queue), 선입선출 줄서기 자료구조

 자료구조로는 '원형 큐'로 구현할 수 있습니다. N개의 원형 큐에서 K마다 삭제하며 순열을 찾을 수 있습니다.

 

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 하지만 굳이 원형 큐를 사용하지 않더라도, 문제를 해결할 수 있습니다. 리스트의 끝에 도달했을 때, 초과한 인덱스만큼 처음부터 다시 시작하면 됩니다.

 

 

 

3. 코드

N, K = map(int, input().split())
numlist = list(range(1, N+1))

res = [] #요세푸스
idx = 0 #인덱스
for t in range(N):
    idx += K - 1
    if idx >= len(numlist):  # 한바퀴를 돌면, 나머지부터 다시 시작
        idx = idx % len(numlist)

    res.append(str(numlist.pop(idx)))
    s = ", ".join(res)
print(f"<{s}>")

 인덱스를 K가 아니라 K-1만큼 증가하면서 요세푸스 순열을 찾습니다. 맨 처음에는 인덱스가 0부터 시작하므로 numlist[K-1]이 맞습니다. 그 이후에는 순열에 들어간 원소를 제거해서 앞의 원소가 비었으므로, K-1만큼 증가한 원소가 다음 K번째 원소가 됩니다.

 K-1만큼 증가하다가 numlist의 인덱스를 벗어나면, 벗어난 만큼( idx % len(numlist) )부터 새로 시작합니다.