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

Thumbnail: Photo by Luiz Felipe S. C. (Unsplash)

queue 계열 자료구조 연습에 항상 보이는 문제 유형입니다.

풀이

python의 경우, 내장 모듈 collections에 deque 자료구조가 사전에 구현되어 있습니다. (물론 list를 바로 사용해도 무방합니다)

이번 풀이는 내장 deque를 사용해 진행했습니다. 문제에서 \(M\)번째 사람마다 방향을 바꾸는 것은, bool 타입 변수인 reverse를 하나 만들어 on/off 해가며 구분했습니다.

내장 deque에는 rotate(n: int=1)라는 메소드가 있는데,
이는 n이 양수일 때는 dequq.appendleft(deque.pop())을,
n이 음수일 때는 deque.append(deque.popleft()) 를 n번 수행하는 것과 동일합니다.

rotate는 reverse가 False라면 \(1 - K\)번, True라면 \(K\)번 수행합니다. K번째 사람은 K-1번 회전해야 제일 앞자리로 오기 때문입니다.

rotate를 사용해 K번째 사람을 deque의 제일 앞자리로 옮기고, 그걸 popleft()로 출력하는 것을 deque가 빌 때까지 반복하면 됩니다.

전체 코드

from sys import stdin
from collections import deque

N, K, M = map(int, stdin.readline().split())
deq = deque(i for i in range(1, N + 1))

cnt = 0
reverse = False
while deq:
    cnt += 1
    deq.rotate(K if reverse else -K + 1)    # K번째 값을 가져오려면 K-1만큼 회전해야 함. 오른쪽으로 회전하려면 -방향으로 회전해야 함.
    # print(deq)
    print(deq.popleft())
    if cnt % M == 0:
        reverse = not reverse

​구현 중에 고민했던 점

초기에는 deq.rotate(K - 1 if reverse else -K + 1)로 생각했는데, 막상 반대 방향으로 제거할 때는 \(K - 1\)이 맞지 않았습니다. 예제랑 대조해보며 \(K\)가 맞다는 점을 찾아 수정했습니다.

이는 값을 deque의 제일 왼쪽에서 제거했기에 (popleft()) 일어난 현상으로, 정방향으로 회전 시에는 왼쪽으로 deque의 값들이 이동하고, 왼쪽에서 값을 제거하기에 \(K-1\)번 이동해야 제거할 값이 제일 왼쪽에 위치하게 됩니다. 그러나, 역방향으로 회전 시에는 오른쪽으로 값들이 이동하지만 값은 왼쪽에서 제거하므로 \(K\)번 이동해야 제거할 값이 제일 왼쪽으로 이동되기 때문입니다.