[백준] 1158번: 요세푸스 문제 (Python)

문제 📄

1158번: 요세푸스 문제

내 풀이 💻

N, K = map(int, input().split())
arr = [i for i in range(1,N+1)]
result = []
index = 0

while len(arr)>0:
    index += K-1
    index %= len(arr)
    result.append(arr[index])
    del arr[index]

print("<",end='')
print(", ".join(map(str, result)), end='')
print(">")

문제에 주어진 것처럼 (N, K)가 (7, 3)일 때를 가정하고 문제를 풀어보자. 주어진 수의 배열이 1부터 7일 때 3번째 숫자를 제거하는 과정은 다음과 같다.

 

1 2 3 4 5 6 7 (3 제거할 차례, arr[2])

1 2 4 5 6 7 (6 제거할 차례, arr[4])
1 2 4 5 7 (2 제거할 차례, arr[1])

1 4 5 7 (7 제거할 차례, arr[3])
1 4 5 (5 제거할 차례, arr[2])
1 4 (1 제거할 차례, arr[0])

4 (4 제거할 차례, arr[0])

 

삭제할 index는 2씩 증가한다. 그리고 2번째에서 3번째 줄로 넘어갈 때 arr[4] 다음 arr[6]를 삭제할 차례가 되는데 그러면 배열의 크기를 넘으므로 (6 % 배열의 크기인 5)를 해서 arr[1]을 삭제할 차례가 오게 된다.

 

이를 일반화 하면

삭제할 index는 K-1 씩 증가하고, K-1씩 증가하는 index를 항상 배열의 크기보다 작게 유지하기 위해 배열의 크기로 나눈 나머지를 index로 한다고 할 수 있다.

Review 🙋‍♀️

• 처음 시도에서는 index += K-1이 아니라 index += 2로 써서 틀렸는데, 예제의 (7, 3)의 경우만 생각하고 만들어서 그렇다. 다음부터는 문제를 풀 때 예제의 특수한 상황의 도움을 받더라도 처음부터 일반화해서 코드를 짜는 연습이 필요할 것 같다.
• 이 문제는 주어지는 입력의 최대 크기가 그렇게 크지 않아서(1~5000) list 방식으로 풀었지만, deque로도 풀 수 있을 것 같다. 0부터 1씩 증가하면서 popleft() 하고 append()를 해서 왼쪽 것을 오른쪽에 더해주다가 K-1번째가 되면 popleft()한 뒤 오른쪽에 다시 추가하지 않고 결과 배열에 추가하는 식으로 하면 될 것 같다.

💡

print(", ".join(map(str, result)), end='')

정수값이 담긴 리스트의 내용물을 쉼표로 연결된 형태로 출력하기 위해

먼저 map으로 리스트의 내용물을 문자열 형태로 바꿔 준 다음, 리스트의 자료를 연결해서 출력해주는 함수인 join을 사용했다.

for문으로 리스트의 값과 ", "을 출력하고 마지막 값은 ", " 없이 따로 result[-1]로 출력해주는 것보다 한 줄로 간편하게 출력할 수 있다.