요세푸스 순열 문제의 deque를 활용한 풀이(복습완료)

송용진·2025년 2월 18일
0

알고리즘과 자료구조

목록 보기
177/190
from collections import deque

# 입력 받기
N, K = map(int, input().split())

# 1부터 N까지의 숫자를 가진 deque 생성
queue = deque(range(1, N + 1))
ans = []

while queue:
    # K-1 만큼 왼쪽으로 회전
    queue.rotate(-K + 1)
    # K번째 사람을 제거하고 결과 리스트에 추가
    ans.append(str(queue.popleft()))

# 결과 출력
print("<" + ", ".join(ans) + ">")

큐를 회전시키는 이유

기본적으로 요세푸스 문제는 원형 구조에서
특정 간격(K)으로 사람을 제거하는 과정

큐를 회전시키는 이유는
요세푸스 문제에서 K번째 사람을 쉽게 찾고 제거하기 위함

큐에서 K번째 사람을 직접적으로 찾기 위해서는
모든 요소를 순회해야 할 수도 있음
하지만, deque의 rotate 메소드를 사용하면
큐의 요소들을 간단하게 회전시킬 수 있음

K만큼 회전시키지 않고 K-1만큼 회전시키는 이유

K번째 사람을 제거하기 위해서는 K-1번 사람을 지나쳐야 함
즉, 현재 위치에서 K번째 사람으로 가기 위해서는 K-1번을 이동해야 함

# K=3
[1, 2, 3, 4, 5, 6, 7] # 초기 큐
[3, 4, 5, 6, 7, 1, 2] # K-1 = 2만큼 회전 후
# popleft()의 출력 결과는 3
profile
개발자

0개의 댓글