C++로 합이 0이 되는 가장 긴 부분 배열의 길이 찾기

N개의 정수로 이루어진 배열이 주어졌을 때, 합이 0이 되는 부분 배열(subarray) 중 가장 긴 것의 길이를 구하는 것이 목표입니다. 만약 합이 0이 되는 부분 배열이 존재하지 않는다면 '0'을 반환해야 합니다.

입력-1 −

N = 8
A[ ] = {15, -5, -1, 5, 1, 4}

출력 −

설명 − 합이 0이 되는 가장 긴 부분 배열은 {-5, -1, 5, 1}이며, 그 길이는 4입니다.

입력-2 −

N = 5
A[ ] = {3, 2, 4, 8, -1}

출력 −

설명 − 합이 0이 되는 부분 배열이 하나도 존재하지 않으므로 출력은 '0'입니다.

문제 해결 접근 방법

이 문제를 해결하는 방법은 여러 가지가 있지만, 선형 시간 O(n) 안에 답을 구할 수 있는 가장 효율적인 방법은 해시 테이블(Hash Table)을 활용하는 것입니다.

핵심 아이디어는 부분 배열의 누적 합(prefix sum)을 Key로, 해당 합이 처음 나타난 인덱스를 Value로 저장하는 해시 테이블을 만드는 것입니다.

배열 전체를 한 번 순회하면서 현재까지의 누적 합을 계산하고, 그 값이 이미 해시 테이블에 존재하는지 확인합니다. 동일한 누적 합이 다시 나타났다는 것은 그 사이 구간의 합이 0이라는 의미이므로, 두 인덱스 사이의 거리로 최대 길이를 갱신할 수 있습니다.

크기 N인 배열을 입력받습니다.
lenMax(int *arr, int size) 함수는 배열과 그 크기를 입력으로 받아 합이 0이 되는 부분 배열의 최대 길이를 반환합니다.
누적 합을 Key로, 인덱스를 Value로 갖는 unordered_map을 사용하여 동일한 합이 반복되는지 검사합니다.
배열 요소를 순회하며 현재 누적 합을 계산합니다. 해당 합이 해시 테이블에 이미 있다면 최대 길이를 갱신하고, 없다면 새로운 합과 그 인덱스를 삽입합니다.
계산된 최대 길이를 결과로 반환합니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
int lenMax(int *arr, int size){
    unordered_map<int,int>mp;
    int sum=0;
    int maxlen=0;
    for(int i=0;i<size;i++){
        sum+=arr[i];
        if(arr[i]==0 && maxlen==0){
            maxlen=1;
        }
        if(sum==0){
            maxlen=i+1;
        }
        if(mp.find(sum)!= mp.end()){
            maxlen= max(maxlen, i-mp[sum]);
        } else {
            mp[sum]=i;
        }
    }
    return maxlen;
}
int main(){
    int N=8;
    int A[N]={15,-2,2,-8,1,7,10,23};
    cout<<lenMax(A,N)<<endl;
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

합이 0이 되는 가장 긴 부분 배열은 {-2, 2, -8, 1, 7}입니다. 따라서 가장 긴 부분 배열의 길이는 '5'가 됩니다.