백준 11866 (python): 요세푸스 문제 0

from collections import deque

N, K = map(int, input().split())
people = deque([])
answer = []
for i in range(1, N+1):
    people.append(str(i))

while people:
    for _ in range(K-1):
        people.append(people.popleft())
    answer.append(people.popleft())
    
print("<" + ", ".join(answer) + ">")

 

# for문 돌릴 필요 없이 하는 법
people = deque([i for i in range(1, n+1)])

 

예전에 알았었는데! 까먹었다

 

 

규칙 찾는 건 재밌어

 

예제를 보면

7, 3 입력 시 <3, 6, 2, 7, 5, 1, 4> 가 나와야 한다

1 2 3 4 5 6 7 이면 1 2 는 건너띄고 3 제거

 

그 다음 단계에선 3 다음 숫자부터 시작하므로

4 5 6 7 1 2 니까 4 5 건너띄고 6 제거

이런 식으로 진행된다.

 

처음 형태를 원 형태 대신 덱 형태의 1 2 3 4 5 6 7 이라고 가정하면

1 2 를 덱의 뒤에 추가하고(popleft 후 append) 3을 제거(popleft)하면

4 5 6 7 1 2 즉, 다음 단계 형태가 된다!

 

규칙은 결국

K-1 개의 숫자를 덱의 뒷부분으로 넘겨준 뒤 맨 앞의 숫자를 정답 리스트에 추가하는 것 !!