[백준 11866번] 요세푸스 문제 0 - 큐

문제 개요

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

 

요세푸스 문제 (Josephus Problem) 는 다음과 같은 규칙을 가진 사람 제거 시뮬레이션 문제입니다.

 

N명의 사람이 원을 이루고 앉아있고, K번째 사람을 순서대로 제거해 나간다고 할 때,

제거되는 사람의 순서를 구하는 문제입니다.

 

예를 들어 N = 7, K = 3 일 경우 제거 순서는 다음과 같습니다.

<3, 6, 2, 7, 5, 1, 4>

 

7명의 사람이 있고 3번째 사람을 계속 제거한다면

• 1, 2, (3), 4, 5, 6, 7 → 3 제거
• 1, 2, (3), 4, 5, (6), 7 → 6 제거 (7부터 시작)
• 1, (2), (3), 4, 5, (6), 7 → 2 제거 
• 1, (2), (3), 4, 5, (6), (7) → 7 제거 
• 1, (2), (3), 4, (5), (6), (7) → 5 제거
• (1), (2), (3), 4, (5), (6), (7) → 1 제거
• (1), (2), (3), (4), (5), (6), (7) → 4 제거

 

문제 해석

1. 1번부터 N번까지 원형으로 앉아 있음
2. 1번부터 시작해서 K번째 사람을 제거
3. 제거 후, 그 다음 사람부터 다시 K번째를 세어 제거 번복
4. 모두 제거될 때까지 진행
5. 제거 순서를 출력 (리스트 형태)

이 문제는 큐를 이용한 로직처럼 보이지만,
파이썬에서는 collections.deque를 사용해 큐의 동작을 시뮬레이션합니다.
특히, rotate()를 이용하면 원형 구조를 쉽게 표현할 수 있어
원형 큐의 동작을 효율적으로 구현할 수 있습니다.

Python의 collections.deque 사용하면 됩니다.

• rotate() : 원형 회전 표현
• popleft() : 맨 앞 제거
• append() : 맨 뒤로 이동

이제 코드로 구현해보겠습니다.

import sys
from collections import deque

def solve():
    input = sys.stdin.readline

    # 입력값을 읽어서 n(사람 수), k(제거 순서)로 나눔
    n, k = map(int, input().split())

    # 1번부터 n번까지 사람들을 덱에 삽입 (초기 상태)
    dq = deque(range(1, n + 1))

    # 제거된 순서를 저장할 리스트
    result = []

    # 덱이 빌 때까지 반복 (모든 사람이 제거될 때까지)
    while dq:
        # K번째 사람을 맨 앞으로 회전시키기 위해 덱을 왼쪽으로 (k-1)만큼 회전
        # 예: K=3이면, 두 명을 뒤로 보내야 3번째 사람이 맨 앞에 옴
        dq.rotate(-(k - 1))

        # 맨 앞의 사람을 제거하고 제거 순서에 추가
        result.append(dq.popleft())

    # 결과 리스트를 출력 형식에 맞게 가공
    print("<" + ", ".join(map(str, result)) + ">")

if __name__ == "__main__":
    solve()

 

 

코드 설명

1. deque(range(1, n + 1)) : 1부터 n까지를 큐로 생성
2. dq.rotate(-(k-1)) : 앞에서 K번째를 맨 앞으로 회전 (양수 : 오른쪽, 음수 : 왼쪽)
3. dq.popleft() : K번째 사람 제거
4. result.append() : 제거 순서 기록

시간 복잡도의 경우에는 rotate, popleft는 O(1) → 총 O(N)이 됩니다.