백준 11866번: 요세푸스 문제 0 - python

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

문제 :

문제에서 (7,3) -> <3,6,2,7,5,1,4>가 나온다고 하였다.
어떻게 나왔는 지 보자.

7은 N, 사람 수를 의미하고 차례로 N만큼 원을 그리며 앉아있다.

3번째 인원 부터 제거 한다.

그 뒤 3다음 숫자인 4가 시작이 되며 4부터 3번째인 숫자 '6' 제거 된다.

이런 식으로 다음 숫자는 2가 제거되고,
다음은 7, 5, 1, 그리고 4 순으로 제거되어
<3,6,7,5,1,4> 라는 결과가 나온다.

N,K 를 받아서 어떤 순서로 나오는 지 알고리즘을 구현하는 것이 해당 문제

deque의 rotate 함수를 이용하면 수월할 것 같다.

초기 시도 :

import sys;
from collections import deque

N , K = map(int, sys.stdin.readline().split())

circle = deque([i for i in range(1, N + 1)])
result = []

for _ in range(N):
    circle.pop(circle[K])
    result.append(circle[K])
    circle.rotate(-K)

print(result)

• deque.pop(deque[K])
  이런 식으로 덱의 K번째 인덱스를 pop 하고 싶었지만 그런식으로 작동하지 않는다.
  그렇기에 rotate로 돌리고 pop,popleft 같은것으로 맨 끝 요소를 pop해야한다.

해답

import sys;
from collections import deque

N , K = map(int, sys.stdin.readline().split())

circle = deque([i for i in range(1, N + 1)]) # deque([1,2,3,4,5,6,7])
result = []

for _ in range(N):
    circle.rotate(-K+1) # K번쨰 숫자를 맨 앞에 안착시켜준다.
    result.append(circle.popleft()) 

print(str(result).replace('[', '<').replace(']', '>'))

• result.append(circle.popleft())
  가 조금 잡기술인데
  circle 덱의 맨 앞 숫자를 빼내고 result 리스트에 저장해주는 코드이다.
  처음엔
  result.append(circle[0])
  circle.popleft()
  이렇게 두 줄의 코드로 작성했는데 저렇게 쌈뽕하게 한줄로도 작성이 되더라.
  append나 pop 안에 deque의 요소 조작 함수도 들어갈 수 있음을 인지해놓자!