백준 알고리즘 파이썬(Python) 1158번 요세푸스 문제

---

1부터 n까지 순서대로 사람을 앉힌 다음에 index번호가 k-1인 사람을 제거 후 temp += k-1 을 통해 temp를 늘려가며 제거한다.

하지만 그러다 보면 temp가 리스트의 len을 넘어가는 순간이 올 수 밖에 없다. (우리가 쓰는 리스트는 원형이 아니므로)

그럴땐 전체 temp를 리스트의 len으로 나눈 나머지의 값으로 temp을 되돌려 놓는다. 그렇게 하면 원형으로 돌아가며 제거하는 것과 같은 효과를 낸다.

 

과정을 손으로 표현해본 것

---

 

코드

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

for i in range(n):
    if len(arr) > num:
        answer.append(arr.pop(num))
        num += k - 1
    elif len(arr) <= num:
        num = num % len(arr)
        answer.append(arr.pop(num))
        num += k -1
        
print("<", ', '.join(str(i) for i in answer), ">", sep = '')