[python] 백준 1158번 요세푸스 문제

백준 1158번 요세푸스 문제

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

문제

풀이

처음에는 count 랑 포인터 이용해서 계속 접근하다가, 예외 사항이 너무 많이 생겨나서 (포인터가 리스트 밖으로 넘어가면 0 으로 다시 백 시켜줘야 한다거나 array 가 팝 될 때마다 원소의 개수를 다시 세어줘야 한다거나...) 머리 폭발. 🌋
생각에 생각을 (한 시간 이상 지속)
갑자기 유레카.
[1,2,3,4,5,6,7]
k-1 만큼 pop 시켰다 append
[3,4,5,6,7,1,2]
이후 pop 한 번
[4,5,6,7,1,2]
안의 원소가 하나도 없을 때 까지 반복
[6,7,1,2,4,5]
팝
[7,1,2,4,5]
이거구나.

from collections import deque

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

while queue:
    for _ in range(k-1):
        a = queue.popleft()
        queue.append(a)

    b = queue.popleft()
    answer.append(b)

formatted_answer = str(answer).replace('[', '<').replace(']', '>')
print(formatted_answer)

📌 주의

[ ] 를 < > 로만 replace 시켜주면 끄읕.