https://www.acmicpc.net/problem/9471
시간 2초, 메모리 128MB
input :
- N K(1 ≤ K ≤ N ≤ 5,000)
output :
- 요세푸스 순열을 출력
싸이클을 어떻게 나타내야 할지.. 에서 막히고
아이템들을 어떻게 제거할지에서 막혔다.
아이템을 제거하는 거를 remove, del 밖에 기억 안 하고 있었는데
pop()을 이용하시는 분이 있어서 이참에 써보았다.
pop()의 경우에는 제거되는 아이템을 리턴해주기 때문에 이런 상황에서 유용하다.
인덱스가 0 일 떄 제거해야하는 인덱스는 2
2 일 때는 4
4일 떄는 6....
리스트의 길이를 인덱스가 넘어버리면 어떻게 해야하는가? 이게 문제 였는데.
나머지 연산을 통해 쉽게 구할 수 있다.
만약 현재 [1, 2, 4, 5, 7] 을 가진 리스트가 존재한다.
idx는 3에 위치 할 때 다음 제거해야 하는 idx는 5인데 이는 존재하지 않고 싸이클을 통해 idx 0을 가리켜야 한다. 이를 보면
idx % len(data)를 통해 구할 수 있음을 알게 된다.
import sys
n, k = map(int, sys.stdin.readline().split())
data = [i for i in range(1, n + 1)]
res = []
idx = k - 1
for i in range(n):
if idx >= len(data):
idx %= len(data)
res.append(data.pop(idx))
idx += k - 1
else:
res.append(data.pop(idx))
idx += k - 1
print("<", end="")
for idx, item in enumerate(res):
if idx == len(res) - 1:
print(item, end="")
else:
print("{}, ".format(item), end="")
print(">")
