[알고리즘][파이썬] 백준_1158_요세푸스 문제

"1158번: 요세푸스 문제" 파이썬 풀이

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

1158번: 요세푸스 문제

 

1번 부터 N명의 사람이 원을 이루며 앉아있고,

K번째 사람을 한 사람씩 제거한다.

제거된 순서를 예제와 같은 형태로 출력하면 된다.

7명이 원을 이룰때 3번째 사람을 제거하는 경우(붉은 색은 제거를 의미함)

 

---

while문 사용

# while문 사용(결과: 맞았습니다!)
N, K = map(int, input().split())

cir = [i for i in range(1, N+1)]
 
rm = []
i = K - 1
while cir:
    if i > len(cir) - 1:
        i = i % len(cir)
    else:
        rm.append(str(cir.pop(i))) # join을 사용하기 위해서 값을 문자열로 append
        i += K - 1

print('<'+', '.join(rm)+'>')

 

cir(circle) 리스트의 값이 pop 되어 빈 리스트가 될 때까지 반복하였다.

이 문제에서 핵심은 i(index)에 해당하는 cir 리스트의 값을 pop 할때,

i 가 리스트의 범위를 벗어 날 경우에 대한 처리이다.

i 를 cir 리스트의 길이(len(cir))로 나눈 나머지가 i 가 되게하여 처리하였다.

 

"IndexError: list index out of range"

로 애먹었던 문제다!