[백준] 11866 : 요세푸스 문제 0 (Python/파이썬)

문제 링크

https://www.acmicpc.net/problem/11866

문제

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

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 ≤ 1,000)

출력

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

예제

입력

7 3

출력

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

---

정답 및 풀이

import sys
from collections import deque

input = sys.stdin.readline

n, k = map(int, input().split())
q = deque(range(1, n + 1))
ans = []

while q:
    q.rotate(-(k - 1))
    ans.append(q.popleft())

print("<" + ", ".join(map(str, ans)) + ">")

1. import sys
   • 표준 입력을 빠르게 처리하기 위해 sys 모듈을 불러온다.
2. from collections import deque
   • 양쪽 끝에서 빠른 삽입·삭제가 가능한 deque를 사용한다.
3. input = sys.stdin.readline
   • 입력 속도를 높이기 위해 기본 input()을 대체한다.
4. n, k = map(int, input().split())
   • 사람 수 n과 제거 간격 k를 입력받는다.
5. q = deque(range(1, n + 1))
   • 1번부터 n번까지의 사람을 덱에 순서대로 저장한다.
6. ans = []
   • 제거되는 순서를 저장할 리스트를 생성한다.
7. while q:
   • 덱에 사람이 남아 있는 동안 반복한다.
8. q.rotate(-(k - 1))
   • 앞에서 k-1명을 뒤로 보내
   • 제거할 k번째 사람을 맨 앞으로 이동시킨다.
9. ans.append(q.popleft())
   • 맨 앞에 온 사람(원래 k번째)을 제거하고
   • 제거 순서를 ans에 저장한다.
10. print("<" + ", ".join(map(str, ans)) + ">")
    • 문제에서 요구한 형식으로 제거 순서를 출력한다.

다른 풀이

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
arr = list(range(1, n + 1))
ans = []
idx = 0

while arr:
    idx = (idx + (k - 1)) % len(arr)
    ans.append(arr.pop(idx))

print("<" + ", ".join(map(str, ans)) + ">")

1. import sys
   • 표준 입력을 빠르게 처리하기 위해 sys 모듈을 불러온다.
2. input = sys.stdin.readline
   • 기본 input() 대신 더 빠른 입력 방식을 사용한다.
3. n, k = map(int, input().split())
   • 사람 수 n, 제거 간격 k를 입력받는다.
4. arr = list(range(1, n + 1))
   • 1번부터 n번까지의 사람을 리스트에 저장한다.
5. ans = []
   • 제거되는 순서를 저장할 리스트를 만든다.
6. idx = 0
   • 현재 기준이 되는 인덱스 위치를 0으로 초기화한다.
7. while arr:
   • 사람이 남아 있는 동안 계속 반복한다.
8. idx = (idx + (k - 1)) % len(arr)
   • 현재 위치에서 k-1칸 이동한 위치를 계산한다.
   • % len(arr)로 리스트를 원형처럼 처리한다.
9. ans.append(arr.pop(idx))
   • 계산된 위치의 사람을 제거하고
   • 제거된 사람 번호를 ans에 저장한다.
10. print("<" + ", ".join(map(str, ans)) + ">")
    • 문제에서 요구한 형식 <a, b, c>로 결과를 출력한다.

---

새롭게 배운 내용 및 느낀점

• rotate(n)
  • n > 0 : 오른쪽 회전
  • n < 0 : 왼쪽 회전
• 예시

q = deque([1, 2, 3, 4, 5])

q.rotate(1) -> [5,1,2,3,4]
q.rotate(2) -> [4,5,1,2,3]

q.rotate(-1) -> [2,3,4,5,1]
q.rotate(-2) -> [3,4,5,1,2]