[BOJ] 11866: 요세푸스 문제 0

BOJ 11866 : 요세푸스 문제 0 바로가기

11866번: 요세푸스 문제 0

 

 

❓문제 설명

 

문제 이해가 조금 어려웠는데, 쉽게 풀면

첫 번째 제거되는 사람은 1번을 기준으로 3번이 K번째이므로 3번이 제거된다.

두 번째 제거되는 사람은 4번을 기준으로 시작하여 K번째인 6번이 제거된다.

세 번째 제거되는 사람은 다시 7번을 기준으로 시작하여 K번째인 2번이 제거된다.

 

 

❗️문제 풀이

양방향 큐인 deque 자료구조를 이용했다.

 

deque의 rotate 함수는 원순열을 돌리는 함수이다.

deque.rotate(양수) 는 시계 방향으로, deque.rotate(음수)는 반시계 방향으로 회전한다.

 

따라서 deque.rotate(K-1)을 이용해 0번째 index를 제거될 값으로 맞추고, 해당 값을 pop으로 제거, 새로운 list에 append 했다.

 

이러면 제거된 값의 다음 값이 바로 기준값이 되기 때문에 바로 다음 K번째 값을 찾아갈 수 있다.

from collections import deque
N, K = map(int, input().split())

people_queue = deque()
answer_list = []
for i in range(N):
    people_queue.append(i+1)

while people_queue:
    people_queue.rotate(-(K-1))
    answer_list.append(people_queue.popleft())

print("<", end="")
for i in range(N-1):
    print(answer_list[i], end=", ")
print(answer_list[N-1], end="")
print(">")