파이썬으로 합이 0인 가장 긴 연속 부분 목록의 길이 찾기

문제 개요

1과 -1 두 값으로만 이루어진 리스트가 주어졌을 때, 원소들의 합이 정확히 0이 되는 가장 긴 연속 부분 목록(sublist)의 길이를 구하는 문제입니다.

예를 들어 입력이 다음과 같다고 해보겠습니다.

nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1]

이 경우 가장 긴 부분 목록은 [-1, 1, 1, -1, 1, -1, 1, -1]이며, 그 합은 0이므로 정답은 8이 됩니다.

접근 방법: 누적 합(Prefix Sum)과 해시 맵

모든 부분 목록을 일일이 확인하는 브루트포스 방식은 O(n²) 이상의 시간이 걸립니다. 대신 누적 합(prefix sum)과 해시 맵(딕셔너리)을 활용하면 O(n) 시간에 효율적으로 해결할 수 있습니다.

핵심 아이디어는 간단합니다. 동일한 누적 합 값이 두 번 나타난다면, 그 두 지점 사이 구간의 합은 반드시 0이라는 점입니다. 따라서 각 누적 합 값이 처음 등장한 인덱스를 저장해 두고, 같은 값이 다시 나타날 때마다 두 인덱스의 차이를 계산하면 됩니다.

알고리즘 단계

1. table := 새로운 빈 딕셔너리 (누적 합 값 → 처음 등장한 인덱스)
2. cs := 0 (현재까지의 누적 합), max_diff := 0 (정답 후보)
3. i를 0부터 len(nums) - 1까지 반복합니다:
   • cs := cs + nums[i]
   • 만약 cs == 0이면, 처음부터 i번째 인덱스까지의 구간 합이 0이라는 뜻이므로 max_diff = max(i + 1, max_diff)로 갱신합니다.
   • 만약 cs가 table에 이미 존재하면, 이전에 등장한 인덱스와 현재 인덱스 사이의 구간 합이 0이므로 max_diff = max(max_diff, i - table[cs])로 갱신합니다.
   • 그렇지 않다면 table[cs] = i로 해당 누적 합이 처음 나타난 위치를 기록합니다.
4. max_diff를 반환합니다.

파이썬 구현 예제

class Solution:
    def solve(self, nums):
        table = {}
        cs = 0
        max_diff = 0
        for i in range(len(nums)):
            cs += nums[i]
            if cs == 0:
                max_diff = max(i + 1, max_diff)
            if cs in table:
                max_diff = max(max_diff, i - table[cs])
            else:
                table[cs] = i
        return max_diff

ob = Solution()
nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1]
print(ob.solve(nums))

입력

[1, 1, -1, 1, 1, -1, 1, -1, 1, -1]

출력

8

복잡도 분석

• 시간 복잡도: O(n) — 리스트를 한 번만 순회하며 각 단계는 상수 시간에 처리됩니다.
• 공간 복잡도: O(n) — 최악의 경우 모든 누적 합 값이 서로 달라 딕셔너리에 n개의 항목이 저장될 수 있습니다.

이처럼 누적 합과 해시 맵을 조합하면 합이 특정 값이 되는 가장 긴 구간을 찾는 유형의 문제를 선형 시간 안에 깔끔하게 해결할 수 있습니다.