[백준 11866] 요세푸스 문제 0

문제

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

11866번: 요세푸스 문제 0

---

아이디어

사람을 제거하는 문제이기 때문에 deque를 이용하면 쉽게 풀 수 있다.

사람을 제거하는 과정은 popleft()를 이용한다. 여기서 핵심은 원을 따라 이다. 이것을 구현하기 위해서는 deque의 rotate()를 이용한다. 

 

1, 2, 3, ..., n 의 사람이 앉아있다고 하자. 1번으로부터 시작한다. 이 때 k번째 사람을 제거되는 것은 지금 위치 기준 (k-1)만큼 시계방향에 있는 사람이 제거된다는 의미와 같다. 즉 deque를 (k - 1)번 반시계 방향으로 돌려준 후에 첫번째 사람을 제거하면 된다. 

 

이 과정을 deque의 길이가 0이 될 때까지(더 이상 남은 사람이 없을 때까지) 반복하면 쉽게 답을 구할 수 있다. 

---

Solution

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

q = deque(lst)
answer = []

while len(q) > 0 : 
    q.rotate(-(k-1))
    add = q.popleft()
    answer.append(add)
    
answer_ = ''
for s in answer : 
    answer_ += str(s) + ', '

print('<' + answer_[:-2] + '>')