[BaekJoon 11866 : Data Structure, Python] - 요세푸스 순열

2021, Oct 19    


백준 11866 요세푸스 순열 : 실버 4



Solution


import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())

def josephus(n, k):
    circle = deque()
    for i in range(1, n+1):
        circle.append(i)
    result = []

    for i in range(n):
        r = k

        while r-1 > 0:       
            circle.append(circle.popleft())
            r -= 1

        result.append(circle.popleft())

    return result

print('<'+', '.join(map(str, josephus(n, k)))+'>')


풀이과정 및 느낀점


FIFO 특성을 반영할 수 있는 큐 자료구조에 대한 문제이다.
우선 k번째 순서 사람을 선택하기 위해 while 문으로 1씩 줄여가면서 가장 앞에 있는 사람을 뒤로 보내준다.
k 번째 사람이 가장 앞에 오면 그 사람을 result 에 append 해준다.
이렇게 n 명의 원순열을 다 완성할 때까지 해당 과정을 반복해주면 된다.