[BOJ/PYTHON] 20301. 반전 요세푸스

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

문제 요약

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

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

반전: M명의 사람이 제거될 때마다 원 돌리는 방향 바꿈

핵심 아이디어

요세푸스 문제를 풀었으면 쉽게 풀 수 있다. 요세푸스 순열에서 반전되는 경우를 추가적으로 핸들링해주면 된다.

파이썬 덱에서는 양수로 rotate할 때는 rotate(k)를 해주면 되는데 음수로 해줄 땐 rotate(-(k-1))을 해줘야 한다.

사람 제거하면서 제거된 사람 수를 1씩 더해주고, m만큼 제거했으면 방향을 바꿔주면 된다.

풀이

# silver3-20301. 반전 요세푸스
import sys 
from collections import deque
input = sys.stdin.readline

n, k, m = map(int, input().split())
q = deque(range(1, n+1))
pop_list = []
removal_number = 0 # 제거된 횟수
rotate_content = -(k - 1) # q.rotate 안에 들어갈 내용

while q:
    if removal_number == m: # 방향 바꿀 때가 옴
        if rotate_content == k:
            rotate_content = -(k - 1)
        else: rotate_content = k
        removal_number = 0
    q.rotate(rotate_content)
    pop_num = q.popleft()
    pop_list.append(pop_num)
    removal_number += 1

print(*pop_list, sep='\\n', end='')

실행 시간

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