[백준] 20301 - 반전 요세푸스

1. 문제

20301번: 반전 요세푸스

2. 개요

일반적인 요세푸스 순열을 만드는 것과 달리 M개의 수가 빠진 이후에는 역으로 돌면서 수를 빼내는 순열을 반전 요세푸스 순열이라고 한다.

N, K, M 이 주어졌을 때, 반전 요세푸스 순열을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

0부터 카운트한다.

수가 빠질때마다 카운트를 1씩 늘려준다.

카운트가 M이 되었다면 카운트를 0으로 초기화하고 역으로 돌린다.

이를 처음 주어진 배열이 빌 때까지 반복한다.

3-2. Python

import sys
from collections import deque

N, K, M = map(int, sys.stdin.readline().split())

cnt = 0

isreverse = 1
nums = deque([i + 1 for i in range(N)])
result = []

while nums:
    if isreverse == 1:
        nums.rotate(-(K-1))

    else:
        nums.rotate(K)

    result.append(nums.popleft())
    cnt += 1

    if cnt == M:
        isreverse *= -1
        cnt = 0

for r in result:
    print(r)