BOJ 20301: 반전 요세푸스- 파이썬(Python)

https://www.acmicpc.net/problem/20301
 

<접근 방법>

대표적인 요세푸스 문제에서 반전 기능이 추가된 형태의 문제이다. 문제에서 제시한 예시를 이용해서 문제를 분석하였다.
(N, K, M) = (7, 3, 4)에서 진행 단계를 표를 이용하여 표현해 보자.
시작 진행 방향은 문제에서 제시한 오른쪽 방향으로 시작한다.
 

=1단계=

 
 

=2단계=

 
=3단계=

 
 
=4단계=

여기서, 원소가 나간 횟수가 m = 4와 같아졌으므로, 이제 방향을 반대인 왼쪽으로 진행한다.

 
=4단계=

 
=5단계=

여기서 주의할 점이 있다. 나가야 할 원소의 순서보다 배열의 원소의 수가 적을 때에는 무한한 길이의 배열로 생각하면 편하다. 위의 이미지에서 4, 5가 진행방향으로 무수히 많이 존재한다고 가정해 보자. 그러면 제거해야 할 원소인 3번째 원소가 5 임을 알 수 있다. 제거할 원소를 찾았다면 이제 이전 단계와 같은 처리를 해주면 된다. 
 
 

<소스 코드>

위의 코드를 이용한 전체 소스 코드 구현 결과이다.
해당 문제를 해결하기 위하여 deque를 이용하였다. 방향을 저장하기 위하여 rev 변수를 선언하였고, 현재 제거한 원소의 개수를 저장하기 위해 rev_count 변수를 선언하였다.

import sys
from collections import deque

n, k, m = map(int, sys.stdin.readline().split())
arr = deque([i for i in range(1, n + 1)])
rev = False
rev_count = 0
count = 0

while arr:
    if len(arr) == 1:
        print(arr.popleft())
    else:
        if rev:
            tmp = arr.pop()
            count += 1
        else:
            tmp = arr.popleft()
            count += 1
        
        if count == k:
            print(tmp)
            rev_count += 1
            count = 0
        else:
            if rev:
                arr.appendleft(tmp)
            else:
                arr.append(tmp)
        
        if rev_count == m:
            rev = not rev
            rev_count = 0