BaekJoon 1158 - 요세푸스 문제 (Python)

지난 문제에 이어서 collections에 존재하는 deque를 적극 이용하는 문제였다.

 

처음에는 deque를 쓰지 않고 해결해볼까 생각했지만, 시간 복잡도나 여러 면에서 deque가 효율적일 것 같아서 처음부터 설계를 deque를 고려하여 진행하였다.

 

deque에는 rotate라는 기능이 존재했고, 지난 번에도 다뤘던 popleft라는 기능도 존재하여 이를 적절하게 사용하면 될 것이라고 생각했다.

 

rotate는 deque를 회전시키는 기능으로, 음수를 입력하면 왼쪽으로 회전한다고 한다.

 

즉, deque([1, 2, 3, 4, 5])가 존재하면 rotate(-1)을 할 경우 deque([2, 3, 4, 5, 1])가 되고, rotate(1)을 할 경우 deque([5, 1, 2, 3, 4])가 된다.

 

이를 적용하여 코드를 완성하였다. (list comprehension도 적극 이용해보았다!)

import sys
from collections import deque
input = sys.stdin.readline    # 시간 초과 error를 해결하기 위한 input함수 재정의

N, K = map(int, input().split())    # 입력을 받을 때 공백을 기준으로 분리한 후 각각을 int 타입으로 변환
num_list = deque(x for x in range(1, N+1))    # number를 1부터 N까지 담고있는 list 생성
result = []    # 결과를 저장하는 list

for _ in range(N):    # N개의 원소를 모두 꺼내므로 N만큼 반복
    num_list.rotate(-K+1)    # deque에 존재하는 rotate 함수를 이용하여 list 회전 (K번째 index를 꺼내므로 회전은 K-1번만 진행)
    result.append(num_list.popleft())    # 가장 좌측에 있는 값을 pop

print('<' + str(result).strip('[]') + '>')    # 예제 출력에 맞게 결과 출력