[파이썬, Python] 백준 1158: 요세푸스 문제

문제

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

코드

n, k = map(int, input().split())
num = list(i for i in range(1, n+1))
ans = []
idx = k - 1

for i in range(n):
    if len(num) <= idx:
        idx = idx % len(num)

    ans.append(num.pop(idx))
    idx += k - 1

print("<", end="")
for i in range(len(ans)-1):
    print(''.join(str(ans[i]) + ", "), end="")
print(ans[-1], end="")
print(">")

설명

우선 n, k를 입력받고, n의 수만큼의 리스트를 생성해 주자.
그리고 idx를 하나 생성해서 k-1로 지정해 주자(3을 빼려면 인덱스는 2가 되어야 함)

이제 반복문을 돌며, 수를 제거하자.

num 리스트의 개수가 idx보다 큰 경우에는,
num의 idx를 pop 한 수를 ans에 넣어주면 된다.

그렇지 않은 경우엔,
idx를 num의 개수로 나눈 나머지가 idx가 된다(3명 중에 5번이면 5 % 3을 한 2가 idx가 된다.)

그리고 idx를 k-1만큼 늘려준다.
이게 처음에 이해가 어려웠는데,
기존 리스트에서 1개가 빠졌으므로 그만큼 빼고 이동한다는 개념으로 이해했다.

반복문을 다 돌면 ans를 출력해 주면 되는데 출력 형식이 복잡하다.
우선 "<"를 출력하고 end=""으로 해주어 공백을 제거하고 출력이 가능하게 하자.
이후 ans의 마지막 수를 제외하고 반복문을 돌며 "숫자, " 형식의 출력을 해준다.
마지막 수는 따로 출력해 주고,
">"를 출력해서 출력 형식을 맞춰준다.