[python] 백준 1158번 요세푸스 문제

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

1158번: 요세푸스 문제

 

 

 

---

 

 

💻 코드

 

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
circle = []
result = []

for i in range(1, n + 1):
    circle.append(i)

temp = k - 1

for _ in range(n):
    if len(circle) > temp:
        result.append(circle.pop(temp))
        temp += k - 1

    else:
        temp = temp % len(circle)
        result.append(circle.pop(temp))
        temp += k - 1

print('<', end='')
print(*result, sep=', ', end='')
print('>')

 

 

 

 

📝 풀이

 

처음에는 문제를 잘못 이해했었다. k번째 사람을 제거하는 데 지운 사람을 기준으로 k번째 사람을 제거해야 하는 것인데 첫 번째 사람을 기준으로 생각했었다.

 

 

 

 

이 문제는 예전에 학교에서 원형 연결리스트를 배웠는데 그 방법을 사용하면 되었었다. 리스트가 인덱스 범위를 벗어나면 다시 맨 앞으로 돌아올 수 있도록 구현하려면 현재 인덱스를 리스트의 길이로 나눈 나머지를 구하면 된다.

 

 

 

먼저 temp를 처음에 k - 1로 잡은 이유는 인덱스는 0부터 시작하기 때문이다. 그리고 현재 가리키는 인덱스가 리스트의 길이보다 큰지 작은지에 의해 temp가 달라지기 때문에 그것을 기준으로 if문을 작성한다. 리스트의 길이가 인덱스보다 크면 그대로 temp에 k - 1을 더해주고 아니라면 temp를 리스트의 길이로 나눠준다. 제거할 인덱스 temp를 구하면 circle 리스트에서 인덱스 temp에 위치하는 값을 pop한다음에 그것을 result 리스트에 넣어주는 것을 반복한다. circle 리스트에 아무것도 없어질 때까지 반복하면 result에 모든 값이 담기게 되고 그것을 출력하면 된다. 

 

 

출력할 때는 리스트의 대괄호를 빼고 출력해야하는데 그 방법은 다양하게 있다.

 

리스트 대괄호[] 없이 출력하기

1. *result

먼저 가장 간단한 방법은 출력할 리스트 앞에 *을 붙이는 것이다. 그러면 대괄호가 사라지는데 , 표시도 사라지게 되므로 그것은 sep=', '을 통해 반점이 나타나도록 할 수 있다. <과 >은 따로 출력해주어야 한다.

 

2. print("<" + str(result)[1:-1] + ">")

문자열로 바꾼 다음 슬라이싱을 하여 출력하는 방법이다. <과 >을 한꺼번에 출력할 수 있다는 장점이 있다.