문제

양의 정수와 음의 정수의 배열이 있다. 합이 0인 부분 배열 중 가장 긴 배열의 길이를 구하라.

예시

입력: A = [15, -2, 2, -8, 1, 7, 10, 23]
출력: 5 (합이 0인 부분 배열은 -2 2 -8 1 7)

풀이

1. 이중 반복문 풀이

def largestSubArrayWithZero(arr):
    result = [0 for _ in range(len(arr))]

    if len(arr) == 1:
        return 1

    for i,num in enumerate(arr):
        subArray = [num]

        for j in range(i+1,len(arr)):
            num2 = arr[j]
            subArray.append(num2)

            if sum(subArray) == 0:
                result[i] = len(subArray)

    return max(result)

하지만 이중 반복문 풀이는 시간제한이 걸리는 테스트 케이스가 많이 존재하기 때문에 추천하는 풀이는 아니다.

위 풀이도 모든 테스트 케이스를 통과하지 못하였으므로, 사전을 이용하여 풀어보자.

2. 사전을 이용한 풀이

누적합과 해시 테이블을 사용한다.

0부터 현재 인덱스까지의 누적합을 표로 나타내보면 다음과 같다.

노란색 부분이 누적합이 같은 부분으로, 누적합이 같은 지점 사이의 합은 0이다.

예외 처리

만약 누적합이 0인 경우라면 어떨까?

첫번째 요소가 0이여서 누적합이 첫번째 인덱스도 포함한 길이로 ans 변수에 할당되어야 하는데, 현재 로직에서는 그렇게 구현하지 않았기 때문에, 예외처리로 누적합 key가 0일 때 초기값을 -1로 설정하여 길이를 하나 증가시켜주도록 설정해주었다.

def maxLen_dict(arr):
    dic = {0:-1} # 첫번째 요소가 0일 때, 누적합 길이 1늘려주기 위해 -1로 할당
    ans = 0
    total = 0

    for i in range(len(arr)):
        total += arr[i]
        if total in dic:
            ans = max(ans, i - dic[total])
        else:
            dic[total] = i
    return ans

누적합을 계산하면서 배열을 순회한다.
해시 테이블의 키를 누적합으로, 값을 누적 합이 처음 나타나는 배열의 인덱스로 저장한다.
누적합이 이전에 등장한 적이 있으면, 그 때의 인덱스와 현재의 인덱스 사이의 부분 배열의 합은 0이다. 그러므로 두 인덱스 사이의 차이를 ans 변수에 업데이트 해준다.

즉, 누적합이 첫 등장했을 때 인덱스와 나중에 등장했을 때 인덱스의 차이가 가장 큰 값을 반환해주는 문제라고 이해하면 된다.