요세푸스 문제에서 사람들이 선택되는 순서를 구하는 문제이다.
알고리즘 분류는 큐에 속하지만 순환식으로 푸는 방법또한 존재한다.
n=7, k=3일 때 1부터 시작해서 3명씩 건너가며 사람들을 삭제한다. 이때 죽은 사람은 건너뛴다.
큐로 푸는 경우에 2164: 카드2 문제의 코드를 조금만 수정하면 쉽게 풀 수 있다.
사람들이 원형으로 앉아있다고 전제하고 있기 때문에 k번째 사람에게로 넘어갈 때 pop한 사람들을 rear에 다시 넣어주어야 한다. while문 안에서 k번 pop과 push를 반복하면서 사람들을 뛰어넘은 후 k번째 사람에게 도달하면 그 사람을 제거한다.
순환함수를 이용하여 푸는 경우에는 우선 모든 값을 리스트에 넣은 후 마지막 한 사람이 남을 때까지 k명째 사람을 제거하는 것을 반복한다.
소스코드
- 큐를 이용해 구하는 방법
import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
queue = deque([x for x in range(1, n+1)])
k -= 1
result = []
while len(queue) > 0:
for i in range(k):
tmp = queue.popleft()
queue.append(tmp)
result.append(queue.popleft())
print("<", end="")
for i in range(len(result)-1):
print(result[i], end=", ")
print(result[len(result)-1], end=">")- 순환식을 이용하는 방법
import sys
n, k = map(int, sys.stdin.readline().split())
list = [x for x in range(1, n+1)]
def Josephus(arr, k, idx):
if len(arr) == 1:
print(arr[0], end=">")
return
idx = ((idx+k)%len(arr))
print(arr[idx], end=", ")
arr.pop(idx)
Josephus(arr, k, idx)
print("<", end="")
Josephus(list, k-1, 0)