출처 | https://www.acmicpc.net/problem/1158

알고리즘 설계

1. 요세푸스 문제에 대한 설명은 해당 부분을 참고하면 된다.

2. 우선 어떤 자료구조를 쓸 것인가?

• 필자는 queue을 이용해서 해당 부분을 저장할 때 mod을 이용하여 pop 하려고 했다. 쉽게 리스트에 저장하는 건 구현 했지만, 안쪽 내부를 3이라는 규칙성을 가지고 pop을 할까? 에 대한 고민이 있었다. --> queue로 구현 시 시간초과가 발생한다.

• 하지만 시간복잡도 및 구조 상 deque를 이용하는게 더 빠르다. 그래서 queue가 아닌 deque로 자료구조를 설계했다.

왜 for문의 조건이 k-1인가?

요세푸스 순열은 주어진 순서로 사람을 제거하는 순열로, k-1까지의 인덱스에 있는 사람은 삭제하지 않고, k번째 사람을 제거한다.

핵심 알고리즘

while que: # 사람이 존재 할 동안 
  for _ in range(k-1):
    que.append(que.popleft()) # 사람을 뒤에 보내는 코드
  rs.append(que.popleft()) # 해당 부분이 k번째 사람을 제거하고 배열 rs에 추가한다.

백준 2164번 : 카드2를 보면 이해하기 쉽다.

from collections import deque


n = int(input())

card = deque()


for i in range(1,n+1): # why? 1234
    card.append(i)

while len(card) > 1:
    card.popleft()
    card.append(card.popleft())

print(card[0])

전체코드

import sys
from collections import deque

input = sys.stdin.readline

n,k = map(int,input().split())
que = deque()
rs = []
for i in range(1,n+1):
  que.append(i)

while que: # 사람이 존재 할 동안 
  for _ in range(k-1):
    que.append(que.popleft()) # 사람을 뒤에 보내는 코드
  rs.append(que.popleft())# 해당 부분이 k번째 사람을 제거하고 배열 rs에 추가한다.

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