요세푸스 순열 - python

Queue 자료구조를 공부하면서 큐를 응용하여 풀 수 있는 간단한 문제

 

 

python 소스코드

from collections import deque

def Josephus(N,K):
    deq = deque([i for i in range(1,N+1)])
    res = []
    cnt = 0
    while len(deq) != 0:
        data = deq.popleft()
        cnt +=1
        
        if cnt % K == 0:
            res.append(data)
            print(res)
        else:
            deq.append(data)
    print(res)

Josephus(7,3)

 

요세 푸스 문제는 N,K 가 주어졌을때 1~N까지 N명 순서대로 원을 이루어 모여 있을때

K번째 사람을 제외하면서 모든 사람이 제외 될 때 제외되는 순서가 요세푸스 순열 이다.

 

 

이미지처럼 제외 되면서 생기는 순열을 저장하면 해결 할 수 있는 문제이다.