백준 1158. 요세푸스 문제

문제 설명

1번부터 N번까지 N명의 사람이 원을 이루어 앉아있고, 양의 정수 K가 주어진다.

순서대로 K번째 사람을 제거하고, 한사람이 제거되면 남은 사람들고 이루어진 원을 따라

이 과정을 계속해나간다.

 

입력

N과 K가 빈 칸을 사이에 두고 순서대로 주어진다.

(1 ≤ K ≤ N ≤ 5,000)

7 3

 

출력

요세푸스 순열을 출력한다.

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

 

코드

n, k = map(int, input().split())
li =[i+1 for i in range(n)]  # [1,2,3,4,5,6,7]
idx = k-1
answer = []
while li:
    answer.append(li[idx])
    del li[idx]
    idx += (k-1)
    if len(li) == 0:
        break
    idx %= len(li)

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

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

 

idx가 변화되는 규칙은 주어진 예제 1을 직접 써보면 이해할 수 있다.

 

answer 리스트에 삭제되는 요소를 저장하고

나중에 한번에 요세푸스 순열 형태로 변환해 출력한다.

 

[ ] 괄호를 < > 괄호로 변경하는 방법은 두 가지가 있는데,

첫 번째 방법은 " ".join() 함수를 사용하는 것이고,

두 번째 방법은 replace('a', 'b') 함수를 사용하는 것이다.

 

replace 함수는 연달아 여러 번 사용할 수 있다.