[BOJ/PYTHON] 1158. 요세푸스 문제

백준 문제 링크: https://www.acmicpc.net/problem/1158

문제 요약

(N, K)-요세프스 순열 구하기

요세푸스 순열: 원을 이뤄 앉아있는 사람 중 k번째 사람을 순서대로 제거.

핵심 아이디어

문제에서 사람이 원을 이뤄 앉아있다는 내용을 읽고 바로 원형 큐를 생각하면 된다.

k번째 사람을 순서대로 제거해야 하는데, rotate로 k번을 돌려줘 제거할 사람을 맨 앞에 오게 만들고, 맨 앞 사람을 pop해주면 된다.

풀이

# silver4-1158. 요세푸스 문제

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

n, k = map(int, input().split())
q = deque(range(1, n+1))
pop_list = []

while q:
    q.rotate(-(k - 1))
    pop_num = q.popleft()
    pop_list.append(pop_num)
print("<", end='')
print(*pop_list, sep=', ', end='')
print(">")

실행 시간

메모리 34228KB, 시간 68ms (python3)