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

jmboy713·2023년 4월 13일
0

코딩테스트

목록 보기
2/27

요세푸스 문제 바로가기

풀이 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='')

출력 결과

profile
Python을 활용한 프로그래밍을 하고있습니다! 데이터분석, 인공지능, Django에 관한 정보를 업로드할 예정입니다. 잘부탁드립니다!!

0개의 댓글