백준 11866번- '요세푸스 문제 0' (PYTHON 풀이)

문제:

 

해당 문제를 보면 이해를 못하시는 분들이 계실 거 같아 간략하게 설명해보겠다.

예제와 같이, 7명의 사람이 순서대로 있고 3번째 사람을 계속 제거한다면

 

1, 2, [3], 4, 5, [6], 7 -> 6 제거 (3 다음에 세번째 위치가 6이니까)
1, [2], [3], 4, 5, [6], 7 -> 2 제거 (6 다음에 세번째는 2)
1, [2], [3], 4, 5, [6], [7] -> 7 제거 (2 다음에 세번째는 7 (남아있는 수 중)
1, [2], [3], 4, [5], [6], [7] -> 5 제거 (7 다음 5)
[1], [2], [3], 4, [5], [6], [7] -> 1 제거
[1], [2], [3], [4], [5], [6], [7] -> 4 제거 (남은 4 제거)

결과적으로 <3, 6, 2, 7, 5, 1, 4> 가 출력된다. 이런식으로 사용자가 정한 순서에 맞게 삭제하고 삭제된 순서대로 출력하면 되는 문제이다.

 

 

풀이:

from collections import deque

N, K = map(int,input().split())
dq = deque(range(1,N+1))
result = []

while dq:
    dq.rotate(-(K-1))
    result.append(dq.popleft())

print("<"+", ".join(map(str,result))+">")

이번 문제도 deque를 활용하여 풀었다.

입력값만큼 dq에 담고 rotate를 활용하여 -2만큼 방향을 돌린다. 부호는 왼쪽으로라는 의미이다.

예를 들어, (1,2,3,4,5,6,7) 이라고 치면 왼쪽으로 두 칸 옮겼으니 (3,4,5,6,7,1,2) 이렇게 돌아간다.

그럼 이 상황에서 popleft를 해서 이 값을 result 리스트에다가 옮긴다. 맨 왼쪽 값을 삭제하라는 의미이므로 3이 삭제되어서 result에 추가된다.

이런 식으로 두 칸씩 옮기면서 왼쪽 끝에 있는 값을 빼내면 원하는 값이 출력된다.

다음번엔 deque를 최대한 활용하지말고 풀어봐야겠다...