백준 1158번 요세푸스 문제 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 1158 요세푸스 문제

1158 요세푸스 문제

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

1158번: 요세푸스 문제

쉽게 설명하자면 원들 돌며 중첩되는 k 번째 사람들을 리스트에서 빼면서 리스트를 비우는 문제로 나머지 개념을 활용하여 원을 돌면 된다.

---

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

circle = [i for i in range(1, n+1)]
result = []
num = k-1

while len(circle):
    if num >= len(circle):
        num = num % len(circle)
    else:
        result.append(str(circle.pop(num)))
        num += k-1

print("<", ", ".join(result), ">", sep='')

---

풀이

circle을 리스트로 1부터 n번까지 추가해준다. 리스트를 사용하는 이유는 pop으로 비우기 위해서다.

출력할 때 빠진 번호들을 순서대로 출력해야 하므로 빈 리스트(result)도 만들어 준다.

num을 선언하는 이유는 계속 3번째 사람을 빼는 것이 아니라 원을 돌며 3번째 사람을 빼야 하기 위해서이다.

while문을 circle에 요소가 없을 때까지 loop을 돌리고

조건문을 작성한다.

num은 한번 루프를 돌때마다 k-1만큼 추가되므로 원의 길이보다 num이 크다면 num을 길이로 나눈 나머지 값을 활용하여 다시 선언해준다.

num이 원안의 수를 제대로 포인팅 한다면 circle에서 num을 pop한 값을 result에 추가한다.

출력은 join과 sep을 활용하여 ,과 띄어쓰기로 출력한다.

---

풀이 결과

1158 풀이 결과