문제 설명
n명의 아이들이 원을 그린 채 서서 풍선을 받기를 기다리고 있다고 가정해 봅시다. 풍선 배분은 인덱스 0부터 시작하여 k번째 아이에게 풍선을 주고, 풍선을 받은 아이는 원을 떠나는 방식으로 진행됩니다. 이후 시계 방향으로 매 k번째 아이가 풍선을 받고 원을 떠나며, 단 한 명의 아이만 남을 때까지 이 과정이 반복됩니다. n과 k가 주어졌을 때, 마지막으로 풍선을 받게 되는 아이의 시작 인덱스를 구하는 것이 목표입니다.
예를 들어 입력이 n = 3, k = 2라고 해봅시다. 이 경우 출력은 1이 됩니다. 첫 번째 라운드에서는 인덱스 2의 아이가 풍선을 받고 원을 떠나므로 원은 [0, 1]이 됩니다. 두 번째 라운드에서는 인덱스 0의 아이가 풍선을 받고 떠나므로 원에는 [1]만 남게 되어, 최종적으로 인덱스 1의 아이가 마지막 풍선을 받습니다.
해결 접근 방법
이 문제는 요세푸스(Josephus) 문제와 유사한 시뮬레이션 방식으로 해결할 수 있습니다. 핵심 단계는 다음과 같습니다.
arr := 0부터 n-1까지의 값을 담은 새 리스트를 생성합니다.
init := 0 으로 초기화합니다.
arr의 크기가 1보다 큰 동안 다음을 반복합니다.
remove := (init + k) mod arr의 크기 로 제거할 위치를 계산합니다.
arr[remove]를 리스트에서 삭제합니다.
init := remove 로 다음 탐색 시작점을 갱신합니다.
반복이 끝나면 arr[0], 즉 마지막에 남은 아이의 인덱스를 반환합니다.
리스트에서 요소를 제거하면 나머지 요소들이 자동으로 앞당겨지기 때문에, 현재 위치에서 k칸 앞의 인덱스를 모듈로 연산으로 계산하는 것만으로 원형 순회를 손쉽게 구현할 수 있습니다.
구현 예제
아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, n, k):
arr = list(range(0, n))
init = 0
while len(arr) > 1:
remove = (init + k) % len(arr)
del arr[remove]
init = remove
return arr[0]
ob = Solution()
n = 3
k = 2
print(ob.solve(n, k))
입력
3,2
출력
1
복잡도 분석
이 알고리즘은 총 n-1번의 제거 연산을 수행하며, 각 제거 시 리스트 삭제에 최대 O(n)의 시간이 걸리므로 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도는 아이들을 저장하는 리스트 때문에 O(n)입니다. n이 매우 큰 경우에는 수학적 공식 기반의 요세푸스 재귀 풀이를 활용하면 O(n) 시간에 해결할 수 있습니다.