[백준] 20301 반전 요세푸스

문제

풀이

첫 번째 풀이
반전 요세푸스라고 하길래, 음 그냥 제거된 사람의 숫자가 M의 배수일때(0 제외) 데크를 reverse 시켜주면 되겠다고 생각하고 풀었는데 시간초과가 발생했다. 왜 시간초과가 발생했는지 고민해봤는데 reverse 함수가 원인일 것이라고 생각했다(나머지 코드는 시간초과가 발생할 이유가 없기 때문)

# 반전 요세푸스 
# cnt % M 이 0 일때, 남아있는 큐를 뒤집는다
import sys
from collections import deque
input = sys.stdin.readline

N, K, M = map(int, input().split())
queue = deque()
for i in range(1, N+1):
    queue.append(i)

ans = [] # 제거된 사람들을 차례로 저장한 것
srCnt = 1 # 탐색 번째 
rmCnt = 0 # 제거된 사람 수

while queue:
    # 제거할 차례면 
    if srCnt % K == 0:
        # 제거하고
        ans.append(queue.popleft())
        rmCnt += 1
        # 아직 남아있으면서, 제거된 사람들이 M 배수면 큐 내 사람들 뒤집음
        if queue and rmCnt != 0 and rmCnt % M == 0:
            queue.reverse()
    # 제거할 차례가 아니면 그냥 앞에껄 빼서 뒤로 넣음
    else:
        v = queue.popleft()
        queue.append(v)
    # 번째 수 증가 시킴
    srCnt += 1

for v in ans:
    print(v)

두 번째 풀이
그래서 생각해보니, 굳이 reverse 를 할 필요는 없고, 데크를 사용하기 때문에 기존의 왼쪽에서 빼고 오른쪽에 넣어줬던 것을 오른쪽에서 빼고 왼쪽으로 넣으면 된다고 생각했다. 따라서 언제 정큐와 역큐를 사용할지 방향을 설정하는 변수를 사용해 처리했다.

import sys
from collections import deque
input = sys.stdin.readline

N, K, M = map(int, input().split())
queue = deque()
for i in range(1, N+1):
    queue.append(i)

ans = [] # 제거된 사람들을 차례로 저장한 것
srCnt = 1 # 탐색 번째 
rmCnt = 0 # 제거된 사람 수
dir = 1 # 1일땐 정큐, -1이면 역큐 
while queue:
    # 제거할 차례면 
    if srCnt % K == 0:
        # 정큐면 왼쪽꺼 제거
        if dir == 1:
            ans.append(queue.popleft())
        # 역큐면 오른쪽꺼 제거
        else:
            ans.append(queue.pop())
        rmCnt += 1
        # 아직 남아있으면서, 제거된 사람들이 M 배수면 큐 방향 뒤집음
        if queue and rmCnt != 0 and rmCnt % M == 0:
            dir *= -1
    # 제거할 차례가 아니면 그냥 앞에껄 빼서 뒤로 넣음
    else:
        # 정큐이면 왼쪽꺼 빼서 오른쪽에 넣음
        if dir == 1:
            v = queue.popleft()
            queue.append(v)
        # 역큐면 오른쪽꺼 빼서 왼쪽에 넣음
        else:
            v = queue.pop()
            queue.appendleft(v)
    # 번째 수 증가 시킴
    srCnt += 1

for v in ans:
    print(v)