[백준] 요세푸스 문제 0

문제보기 - https://www.acmicpc.net/problem/11866

문제명    - 요세푸스 문제 0

난이도    - S4

문제유형 - 구현

풀이일자 - 25.03.23

 

📌 문제 탐색하기

• 1번부터 N번까지 N명의 사람이 원을 이루어 앉아 있음
• 순서대로 K번째 사람을 제거하는 작업을 반복하여 모든 사람이 제거될 때까지 진행함
• 첫 줄에 N과 K가 주어진다.
  • (1 ≤ K ≤ N ≤ 1,000)
• N과 K가 주어지면 (N, K)-요세푸스 순열을 출력해야 함
  • < > 기호 안에 출력해야 함

 

🛠 시간복잡도 확인

• 큐(Queue)를 사용하여 O(N)에 해결 가능!

 

📌 코드 설계하기

1. N,K 입력 받기
   • map(int, sys.stdin.readline().split())
2. 큐 초기화
   • queue = deque(range(1, N + 1))
3. 요세푸스 순열 만들기
   • rotate(-(K - 1)) -> K번째 사람이 앞으로 오도록 회전(K-1번 왼쪽으로 회전)
4. 결과 출력
   • print("<" + ", ".join(map(str, result)) + ">")

 

📌 정답 코드(1회차)

from collections import deque
import sys

# 1. N,K 입력 받기
N, K = map(int, sys.stdin.readline().split())

# 2. 큐 초기화
queue = deque(range(1, N + 1))
result = []

# 3. 요세푸스 순열 만들기
while queue:
    queue.rotate(-(K - 1))
    result.append(queue.popleft())  # K번째 요소 제거

# 4. 결과 출력
print("<" + ", ".join(map(str, result)) + ">")

•