[python] 백준 #1158 요세푸스 문제 재풀이

올해 초에 이 문제를 푼 적이 있었는데, 이번에 다시 풀 기회가 생겨 다시 한번 풀어보았다.

 

01.이전에 푼 방법 --> O(N) 72ms

https://yeon-woo-kim.tistory.com/83

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

02. 새로 푼 방법 --> O(N) 3996ms

 

[ 자료구조 ]

큐

 

[ 접근 방법 ]

que를 하나 만들어, k 전까지 pop을 해서 que의 뒤에 추가해 준뒤 k번째의 원소를 popleft하여 빼주었다.

 

[ etc ]

이 글을 쓰는 이유는 하나다.. 요세푸스 2가 있는데 그 문제를 풀다가 시간초과 때문에 틀린 기억이 선명해서,,

과거의 풀이가 72ms로 굉장히 효율적으로 풀었다고 생각했는데,

요세푸스 2를 풀려면 세그먼트 트리를 적용해야한다.!

그땐 그냥 넘겼는데 이번 기회에 세그먼트 트리를 다시 정리해봐야겠다.꼭꼭..

from collections import deque
N, k = map(int, input().split())
que1=deque([i+1 for i in range(N)])
result=[]

while que1:
    for i in range(k-1):
        q=que1.popleft()
        que1.append(q)
    result.append(que1.popleft())

result = ', '.join(map(str, result))
print(f'<{result}>')