백준 11866번 파이썬 문제풀이(요세푸스 문제 0)

 

---

큐로 구현하면 간단하게 풀 수 있다. 우선 리스트의 원소들을 큐에 담고 0 부터 k-1번째까지의 원소를 맨뒤로 보내고 k 번째 원소(그렇게 되면 k 번째 원소가 맨앞에 오게 됨으로)를 출력할 리스트에 차근차근 담아준다.

 

from collections import deque

N, K = map(int, input().split())
K = K - 1
array = [x for x in range(1, N + 1)]
yosepoose = []  # 출력할 요세푸스 배열 선언

queue = deque(array)

while True:

    for i in range(K):  # k - 1 번째 까지 돈다.
        queue.append(queue.popleft())  # 큐의 맨 앞의 원소를 큐의 맨뒤로 순서대로 보낸다.
    yosepoose.append(queue.popleft())  # 출력할 리스트에 맨앞 원소부터 넣어 준다.

    if len(yosepoose) == len(array):  # 만약 요세푸스 원소의 길이가 입력받은 배열의 길이와 같아졌다면 반복문 탈출
        break

print('<' + ', '.join(map(str, yosepoose)) + '>')

 

재귀로 구현한 풀이도 있다. 알아두면 유용하다.

import sys

sys.setrecursionlimit(100000)

N, K = map(int, input().split())

array = [x for x in range(1, N + 1)]
result = []
index = 0  # 초기 index값 0


def move(index):
    # index가 0일때는 1번사람을 출력해야 하므로 index + 1을 해준다.
    # 만약 N이 7일 때 7번사람을 출력하기 위해서는 index가 0일때 이다.
    index = (index + 1) % N

    if array[index] != 0:  # 만약 아직 방문하지 않았다면
        return index  # 해당 index 반환
    else:  # 방문했다면
        return move(index)  # 그다음 인덱스로 넘어간다


for i in range(N):  # 총 N번 돌아야한다.
    for j in range(K):  # 무조건 K번 인덱스를 이동시켜야하기 때문에 K번 돈다.
        index = move(index)

    if index == 0:  # 만약 결과 index가 0이란건 7번째 사람을 뜻하므로
        result.append(N)  # N을 result에 넣어준다.

    else:  # 그 밖의 경우는 1~6 까지 이므로
        result.append(index)  # 그 값을 result값에 넣어준다.

    array[index] = 0

print('<' + ', '.join(map(str, result)) + '>')