Python으로 부분 리스트의 합이 전체 리스트 총합보다 큰지 확인하는 프로그램

숫자로 이루어진 리스트 nums가 주어졌을 때, 그 합이 리스트 전체의 총합보다 엄격하게 큰 부분 리스트(sublist)가 존재하는지 확인하는 문제입니다.

예를 들어 입력이 nums = [1, -2, 3, 4]라면 결과는 True입니다. 리스트 전체의 합은 6이고, 부분 리스트 [3, 4]의 합은 7로 전체 합보다 크기 때문입니다.

문제 해결 접근 방법

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

• total := nums 요소들의 총합을 구합니다.
• s := 0으로 초기화합니다.
• nums의 각 요소 i에 대해 왼쪽부터 순회하며:
  • s := s + i 로 누적합을 갱신합니다.
  • s < 0이면 True를 반환합니다. (앞부분의 합이 음수라면, 그 부분을 잘라낸 나머지 뒷부분의 합이 전체 합보다 커집니다.)
• s := 0으로 다시 초기화하고, i := len(nums) - 1로 설정합니다.
• i > -1인 동안 오른쪽부터 순회하며:
  • s := s + nums[i] 로 누적합을 갱신합니다.
  • s < 0이면 True를 반환합니다. (뒷부분의 합이 음수라면, 그 부분을 잘라낸 앞부분의 합이 전체 합보다 커집니다.)
  • i := i - 1 로 인덱스를 감소시킵니다.
• 모든 검사를 통과하면 False를 반환합니다.

동작 원리

핵심 아이디어는 간단합니다. 임의의 연속된 부분 리스트의 합이 전체 합보다 크려면, 그 부분 리스트를 제외한 나머지 영역(왼쪽 접두사 + 오른쪽 접미사)의 합이 반드시 음수여야 합니다. 따라서 왼쪽에서 시작하는 접두사 누적합 또는 오른쪽에서 시작하는 접미사 누적합 중 하나라도 음수가 되는 지점이 존재한다면, 조건을 만족하는 부분 리스트가 반드시 존재합니다. 두 방향의 스캔만으로 모든 경우를 판별할 수 있으므로 시간 복잡도는 O(n)입니다.

구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

class Solution:
    def solve(self, nums):
        total = sum(nums)
        s = 0
        for i in nums:
            s += i
            if s < 0:
                return True
        s = 0
        i = len(nums) - 1
        while i > -1:
            s += nums[i]
            if s < 0:
                return True
            i = i - 1
        return False

ob1 = Solution()
nums = [2, -4, 3, 5]
print(ob1.solve(nums))

입력

[2, -4, 3, 5]

출력

True

결과 분석

리스트 [2, -4, 3, 5]의 전체 합은 6입니다. 왼쪽부터 누적합을 계산하면 2 → -2가 되어 음수가 되는 순간이 발생하므로 즉시 True를 반환합니다. 실제로 앞의 두 요소 [2, -4]를 제외한 부분 리스트 [3, 5]의 합은 8로, 전체 합 6보다 엄격하게 큽니다.