[백준 / Python] 1158번 요세푸스 문제 | 초코더

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

1158번: 요세푸스 문제

접근법

이 문제에서는 원의 인덱스가 어떻게 변하는지 살펴보는 것이 핵심이었습니다.

만약 3번째 인덱스를 제거한다고 생각하면, 처음 3번째 사람이 제거된 후에는 제거된 사람 다음사람부터 새로운 시작 인덱스가 되는 것을 이해해야 합니다. 즉, temp+=k-1 이부분에 해당합니다.

 

그리고 temp를 그냥 넣으면 안되는 이유는 2명이 있을때 3번째 사람을 제거하려면 1 2 1 이런식으로 세어지기 때문에 꼭 %를 이용해야합니다. 즉, temp=temp%len(nums) 이부분에 해당합니다.

 

나의 풀이

import sys
n,k=map(int,sys.stdin.readline().split())
nums=[p for p in range(1,n+1)]
ans=[]
temp=k-1
for i in range(n):
    #위치가 리스트를 넘지않으면
    if len(nums) > temp:
        #제거하고 답으로 추가
        ans.append(nums.pop(temp))
        #temp번째 수가 제거 되었고 (k-1)만큼 다음수가 시작이므로
        temp+=k-1
    #위치가 리스트를 넘으면
    elif len(nums) <= temp:
        temp = temp%len(nums)
        # 제거하고 답으로 추가
        ans.append(nums.pop(temp))
        # temp번째 수가 제거 되었고 (k-1)만큼 다음수가 시작이므로
        temp += k-1
print('<',end='')
for i in ans:
    if i==ans[-1]:print(i,end='')
    else: print("%s, "%(i),end='')
print('>',end='')