[baekjoon] 백준 1158번(파이썬): 요세푸스 문제

문제

1158번: 요세푸스 문제

알고리즘

- n명의 사람을 다 제거할 때까지 반복한다.

- 반복하면서 제거할 인덱스를 더해줘 제거할 인덱스의 위치를 바꿔준다.

- 인덱스의 크기가 남은 큐에 길이보다 크다면 인덱스의 크기를 나눠 나머지로 바꾼다.

- 큐에서 해당 인덱스를 제거하고 제거한 요소를 리스트에 추가한다.

코드

import sys

n, k = map(int, sys.stdin.readline().split())

queue = [i for i in range(1, n + 1)]
temp = []
index = 0 # 제거할 인덱스

while queue:
    # 제거할 인덱스를 더해서 제거할 인덱스 위치를 바꾼다.
    index += k - 1

    # 인덱스의 크기가 남은 큐에 길이보다 크다면
    if index >= len(queue):
        # 인덱스의 크기를 나눠 나머지로 바꾼다.
        # 한바퀴 돌았기 때문
        index %= len(queue)

    # 큐에서 해당 인덱스를 제거하고 제거한 요소를 리스트에 추가한다.
    temp.append(str(queue.pop(index)))

# sep 함수를 통해 소괄호 공간을 없앤다.
print("<", ", ".join(temp), ">", sep="")

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법