(BOJ) 11866. 요세푸스 문제 0

요세푸스 문제 바로가기

풀이 Idea

• 원형 큐를 이용해서 풀어야 할것 같은 문제.
• 인원을 빼면 그 다음사람이 첫번째 사람이 된다. → 3번째 사람을 pop해서 새로운 리스트에 넣어준다.
• 리스트를 넘어가면 처음으로 돌아와야 하는데?? → 원형 큐.
  • 리스트를 넘어가면 넘어간 숫자 / 원형큐의 capacity의 나머지로 index를 바꿔준다!
• 리스트가 빌때까지 반복문을 통해 제거하면 될 듯 하다!

import sys

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

circle_queue=[i+1 for i in range(N)]# 원형 큐를 만들어 준다. ( 단순 리스트를 이용한 큐 )

prior=0 # 시작 index
result=[] # 순열을 담을 리스트
while circle_queue!=[]: # 원형 큐가 빈 리스트일때까지
    prior+=(K-1) # k번째 수로 이동
    prior=prior%N # k가 N을 벗어났을수도 있으니 나머지로 변환
    result.append(circle_queue[prior]) # 해당 숫자를 append함
    circle_queue.remove(circle_queue[prior]) # 원형 큐에서 제거
    N-=1 # 원형 큐에서 1개가 빠져나갔으니 원형 큐 갯수에서 -1 해줌.
    
# 출력 조건
print('<',end='')
print(*result,sep=', ',end='')
print('>',end='')

출력 결과