[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 명의 원순열을 다 완성할 때까지 해당 과정을 반복해주면 된다.