159. 11866(요세푸스 문제 0) - 파이썬

from collections import deque
import sys
input = sys.stdin.readline

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

queue = deque(list(i for i in range(1, N+1)))
answer = []

while queue:
    for i in range(K-1):
        queue.append(queue.popleft())
    answer.append(queue.popleft())

print("<", end="")
for i in range(len(answer)-1):
    print(str(answer[i]) + ", ", end="")
print(str(answer[-1]) + ">")

문제요약

요세푸스 순열을 완성하시오.

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=attractorlim&logNo=221030930874 

요세푸스문제 Josephus problem 순열

설명

간단히 반복적으로 K번째를 제거하라는 말이다.

큐를 이용해 K번째를 제거하기 위해서는 K번째 보다 앞에있는 것은 뒤로 보내준다.

입력이

다음과 같을때,

다음과 같이 값을 구할 수 있다.

 

설명을 하면, 큐를 이용했을 때 큐 안에 값이 없을 때 까지 K-1번 앞에 있는 값을 뒤로 보내고, K번째 되었을 때 값을 꺼내

다른 곳에 저장한다.

 

queue = deque(list(i for i in range(1, N+1)))

값을 1부터 N까지 저장한다.

while queue:
    for i in range(K-1):
        queue.append(queue.popleft())
    answer.append(queue.popleft())

while queue:

큐 내에 값이 있다면 계속 반복한다.

    for i in range(K-1):
        queue.append(queue.popleft())

K-1번 앞에 있는 값을 뒤로 보내는 행위를 반복한다.

    answer.append(queue.popleft())

K번째에 앞에 있는 값을 answer에 저장한다.

 

print("<", end="")
for i in range(len(answer)-1):
    print(str(answer[i]) + ", ", end="")
print(str(answer[-1]) + ">")

출력 형식에 맞게 작성하기 위해 쓴 것이다.