[백준/파이썬] 1158: 요세푸스 문제

문제 풀러 가기

1158번: 요세푸스 문제

✅문제 풀이

처음에는 뭔가 수학적인 규칙이 있나 생각하다가(나누기한 나머지 등..) 예제를 풀어봤는데 안맞았다ㅠ
문제 분류를 보니 '큐'가 있어서 아이디어가 떠올랐다.

그냥 원이 돌 듯이.. 큐로 구현하면 되는 것이었다.
python deque를 사용했다. 앞쪽으로도, 뒤쪽으로도 요소를 삽입/삭제할 수 있다.

원으로 돌 때도 맨 뒤에 있던 것 다음에 맨 앞에 있는 걸로 오니까.. deque로 이걸 구현할 수 있었다.(맨 앞에서 꺼내서, 맨 뒤로 넣기)

K번째 사람이 제거되면, deque에서 제거했다.

출력 형식이 특이해서 주의해야 한다! (<3, 6, 2, 7, 5, 1, 4>)

👩‍💻코드

from collections import deque

N, K = map(int,input().split())

q = deque(list(k+1 for k in range(N)))
ans = []

cnt = 0
while q:
    cnt += 1

    tmp = q.popleft()

    if cnt == K:
        ans.append(tmp)
        cnt = 0
    else:
        q.append(tmp)

print('<', ', '.join(map(str,ans)),'>',sep='')