[BOJ] 1158. 요세푸스 문제 Python 풀이

문제 출처 : https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1

7 3

예제 출력 1 

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

풀이

원형 큐(Ring Buffer)를 생각하면 쉽게 풀 수 있는 문제입니다. 문제를 그림으로 표현해보면,

초기 상태

위 상태가 1번부터 N번까지 N명의 사람이 원을 이루며 앉아있는 초기 상태입니다. 이후 위 예시에 주어진 K번째 사람을 제거하면 3번째 사람이 제거되게 됩니다.

3번째 사람이 제거된 상태

3번째 사람이 제거되면, 제거된 사람 이후부터 3번째 사람을 다시 세게 됩니다. 두 번째로는 6번째 사람이 제거됩니다.

6번째 사람이 제거된 상태

6번째 사람이 제거되면, 제거된 사람 이후부터 3번째 사람을 다시 셉니다. 이때 마지막 사람인 7을 만나면 다시 첫 번째 사람인 1로 돌아가야 합니다. 배열이라고 생각하면 어렵지만, 원형이라고 생각하면 상상하기 좀 더 수월해집니다.

2번째 사람이 제거된 상태

2번째 사람을 제거하고, 제거된 사람을 제외한 나머지 사람들 중에서 3번째 사람을 세게 됩니다. 위와 같은 사이클을 반복하게 됩니다. 제가 작성한 코드는 아래와 같습니다.

# 자료 구조, 큐
import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
arr = deque([i for i in range(1, n + 1)])
answer = []

# 큐가 존재하는 동안
while arr:
    # 음수면 왼쪽, 양수면 오른쪽으로 회전
    # 큐를 회전하며 맨 왼쪽에 있는 수 제거
    arr.rotate(-(k - 1))
    answer.append(arr.popleft())

print(str(answer).replace('[', '<').replace(']', '>'))

python의 collections 모듈에서 양방향으로 데이터를 처리할 수 있는 deque 자료구조를 쉽게 구현할 수 있도록 지원합니다. popleft(), appendleft()와 같은 기능을 사용할 수 있습니다.

 

1. 사람 수 n과 양의 정수 k를 입력 받습니다.

2. 입력받은 사람 수 n만큼 리스트를 만들고([1, 2, 3, 4, 5...]) deque로 선언해줍니다.

3. 요세푸스 순열을 저장할 리스트 answer를 초기화시킵니다.

4. arr이 존재하는 동안 아래와 같은 과정을 반복합니다.

  4-1. arr을 k - 1만큼 왼쪽으로 회전합니다. ex) k=3이고 [1, 2, 3, 4, 5] -> [3, 4, 5, 1, 2]

  4-2. arr의 가장 왼쪽에 위치하는 수를 제거하고 요세푸스 순열 answer에 넣어줍니다.

5. 완성된 순열을 출력합니다.