[Python] 백준 1158번 - 요세푸스 문제

문제

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

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

내 코드

import sys

N, K = map(int, sys.stdin.readline().split())
yose = [_ for _ in range(1, N+1)]
answer = []
tmp = K - 1
while yose:
    if tmp >= len(yose):
        tmp = tmp - len(yose)
        continue
    answer.append(yose.pop(tmp))
    tmp += K - 1

print('<', end='')
for i in range(len(answer)):
    print(answer[i], end='')
    if i != len(answer)-1:
        print(end=', ')
print('>')

 

맨 처음에는 따로 변수를 안 만들고 K를 증감시켜서 해봤는데 K가 상수이다 보니 중간에 오류가 있었다.
그래서 tmp라는 변수를 만들어서 index를 따라가는 변수로 사용했다.

또, tmp = tmp - len(yose) 로직을 거쳤을 때 tmp와 len(yose)의 값이 같아지는 경우가 발생했다.
예를 들어 tmp가 4고 len(yose)가 2라면, tmp가 2가 돼서 len(yose)와 같아진다.
이러한 경우 index error가 발생
continue 함수를 사용하여 tmp가 작아질 때까지 반복했다.

마지막으로, 출력을 저렇게 하는게 맞나 싶어서 찾아봤다.

print("<", ", ".join(answer), ">", sep="")

 

역시나 이런 간단한 방법이 있었다.

 

queue를 이용해서 풀지는 않았지만, 일단 맞았으니 오케이...

원형 queue를 이용해서 (K=3이라고 가정)
<1, 2, 3, 4, 5, 6, 7> push-> <2, 3, 4, 5, 6, 7, 1> push-> <3, 4, 5, 6, 7, 1, 2> pop-> <4, 5, 6, 7, 1, 2> ...
이런 식으로 푸는 사람도 있었다.
인덱스는 나머지 연산을 이용해서 했다.