Python – 모든 접두사 합이 양수가 되도록 리스트 앞에 삽입할 최솟값 구하기

숫자로 이루어진 리스트 nums가 주어졌을 때, 이 리스트의 맨 앞에 삽입하여 결과 리스트의 모든 접두사 합(prefix sum)이 0보다 크도록 만드는 최소 양수 값을 구하는 문제입니다.

예를 들어 입력이 nums = [3, -6, 4, 3]이라면 출력은 4가 됩니다. 4를 삽입하면 리스트는 [4, 3, -6, 4, 3]이 되고, 접두사 합은 [4, 7, 1, 5, 8]로 모든 값이 0보다 크기 때문입니다.

문제 해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

nums의 맨 앞(인덱스 0)에 0을 삽입합니다.
인덱스 1부터 리스트 끝까지 반복하면서 각 요소에 바로 앞 요소의 값을 더해 누적합(접두사 합)을 계산합니다.
1에서 리스트 전체의 최솟값을 뺀 값을 반환합니다.

동작 원리

맨 앞에 0을 삽입하기 때문에 리스트의 최솟값은 항상 0 이하가 됩니다. 원래 리스트의 최소 접두사 합이 m이라면, 삽입하는 값 x는 x + m ≥ 1, 즉 x ≥ 1 − m을 만족해야 하며, 그중 가장 작은 값이 바로 1 − min(nums)입니다. 이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)입니다.

예제 코드

def solve(nums):
   nums.insert(0, 0)
   for i in range(1, len(nums)):
      nums[i] += nums[i - 1]
   return 1 - min(nums)

nums = [3, -6, 4, 3]
print(solve(nums))

입력

[3, -6, 4, 3]