(Python) 백준 11866번 - 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

풀이

오랜만에 정렬이 아닌 다른 유형의 문제를 풀다보니 조금 헤메었다.

리스트를 사용해 간단한 원형 큐와 원형 큐에서의 삭제를 구현하면 되는 문제였다.

import sys
def josephus(arr, k, order):  # N명의 사람이 저장된 arr에서 (N, K)-요세푸스 순열을 order에 저장
    arrow = 0  # 제거될 사람의 번호
    while len(arr) != 0:  # 모든 사람이 제거될 때까지
        arrow += (k-1)  # 다음 K번쨰 사람을 지목 (제거된 사람들 자리를 채우기 위해 한 칸씩 당겨지므로 k-1)
        if arrow >= len(arr):  # 원형 큐처럼 구현하기 위함
            arrow %= len(arr)  # 인덱스 범위를 넘어서게 되면 전체 길이로 나눈 나머지로 재설정
        order.append(arr[arrow])  # 제거될 사람을 order에 저장
        arr.pop(arrow)  # 해당 사람을 제거

n, k = map(int, sys.stdin.readline().split())
arr = []
order = []
for i in range(n):
    arr.append(i+1)
josephus(arr, k, order)  # 요세푸스 배열 계산
print('<'+str(order)[1:-1]+'>') # '['와 ']'를 제거하기 위해 [1:-1] 사용