code

# Topic : Data_Structure _ 요세푸스 문제
#
# PyPy 3 : 116ms

import sys

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

yoseps = [i+1 for i in range(N)]  # 1~N 의 list 생성 
result = list() # 결과를 저장할 list

i = 0 # yoseps list를 돌아다닐 index
while len(yoseps) != 0: # yoseps list의 모든 요소가 사라져 길이가 0이 될때까지 loop 
  i = (i+K-1) % len(yoseps) # * 직전 index 위치에서 K만큼 이동(+K-1)후 list의 길이로 mod 연산(인덱스 넘어가면 리스트 앞쪽으로 전환)
  result.append(yoseps[i])  # 해당 요소를 result에 저장 후
  del yoseps[i] # yoseps list에서는 없애준다.

# < ~ > 형식으로 만들어준다.
result = str(result)
result = result.replace('[','<')  
result = result.replace(']','>')
print(result)

메모리 : 114328 KB 시간 : 116 ms

접근

원형의 접근 순서를 mod 연산으로 처리하고 yoseps list에서 하나씩 제거해나가면서 index를 돌리면 되겠다 생각.

다른 접근

1. Queue 로 푼 사람이 있는데 이 문제에 한에서는 비효율적이라고 한다.

2. 양방향 Queue(deque)를 사용하여 풀 수 있다.

   • deque methods

   from collections import deque
   
   N, K = map(int,sys.stdin.readline().split())
   
   yoseps = deque([i+1 for i in range(N)])
   result = list() # 결과를 저장할 list
   
   # 중식당 테이블처럼 원하는 요소를 내 앞으로 가져다 놓는 형식이다. 
   for i in range(N - 1):
   	for _ in range(K - 1):
   		yoseps.append(yoseps.popleft()) # 좌측에 있는 요소를 우측에 붙인다.(K번째 움직인 요소를 맨 좌측에 놓기 위해서)
   	result.append(yoseps.popleft()) # 현재 가장 왼쪽에 있는 요소를 result에 저장
   
   # < ~ > 형식으로 만들어준다.
   result = str(result)
   result = result.replace('[','<')  
   result = result.replace(']','>')
   print(result)
   

   메모리 : 248044 KB 시간 : 480 ms

   ⇒ 근데 이 친구 메모리랑 시간은 더쓴다.