이 문제에서는 정수 값으로 구성된 배열이 주어지고, 그중에서 요소들의 합이 0이 되는 모든 하위 배열(subarray)을 찾아 출력해야 합니다.
먼저 예시를 통해 문제를 살펴보겠습니다.
입력: array = [-5, 0, 2, 3, -3, 4, -1] 출력: 합이 0인 하위 배열은 인덱스 1부터 1까지 → [0] 합이 0인 하위 배열은 인덱스 0부터 3까지 → [-5, 0, 2, 3] 합이 0인 하위 배열은 인덱스 3부터 4까지 → [3, -3] 합이 0인 하위 배열은 인덱스 0부터 6까지 → 배열 전체 합이 0인 하위 배열은 인덱스 4부터 6까지 → [-3, 4, -1]
방법 1: 완전 탐색(Brute Force)
가장 직관적인 방법은 가능한 모든 하위 배열을 하나씩 검사하는 것입니다. 각 하위 배열의 합을 계산해서 0이 되면 해당 구간을 출력합니다. 이 방법은 이해하기 쉽다는 장점이 있지만, 시간 복잡도가 O(n²)이므로 배열의 크기가 커지면 비효율적입니다.
방법 2: 해싱(Hashing)을 활용한 효율적인 풀이
더 나은 해결책은 접두사 합(prefix sum)과 해시 테이블을 함께 사용하는 것입니다. 핵심 아이디어는 다음과 같습니다.
- 배열을 순회하면서 현재 위치까지의 누적 합(sum)을 계산합니다.
- 누적 합이 0이 된다면, 인덱스 0부터 현재 인덱스까지의 하위 배열의 합이 0이라는 의미입니다.
- 동일한 누적 합이 해시 테이블에 이미 존재한다면, 그 지점 바로 다음(i+1)부터 현재 인덱스(i)까지의 구간 합은 반드시 0입니다.
- 누적 합이 해시 테이블에 없다면, 현재 인덱스 정보와 함께 저장해 둡니다.
알고리즘 단계
1단계: 누적 합을 저장할 sum 변수를 만듭니다. 2단계: sum이 0이면, 인덱스 0부터 현재 인덱스까지의 하위 배열이 조건을 만족합니다. 3단계: 현재 sum이 해시 테이블에 이미 존재하는지 확인합니다. 4단계: sum이 존재하면, i+1부터 n까지의 하위 배열의 합은 0입니다. 5단계: 그렇지 않으면 현재 sum을 해시 테이블에 삽입합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
vector< pair<int, int> > findSubArrayWithSumZero(int arr[], int n){
unordered_map<int, vector<int> >map;
vector <pair<int, int>> out;
int sum = 0;
for (int i = 0; i < n; i++){
sum += arr[i];
if (sum == 0)
out.push_back(make_pair(0, i));
if (map.find(sum) != map.end()){
vector<int> vc = map[sum];
for (auto it = vc.begin(); it != vc.end(); it++)
out.push_back(make_pair(*it + 1, i));
}
map[sum].push_back(i);
}
return out;
}
int main(){
int arr[] = {-5, 0, 2, 3, -3, 4, -1};
int n = sizeof(arr)/sizeof(arr[0]);
vector<pair<int, int> > out = findSubArrayWithSumZero(arr, n);
if (out.size() == 0)
cout << "No subarray exists";
else
for (auto it = out.begin(); it != out.end(); it++)
cout<<"Subarray with sum 0 is from "<<it->first <<" to "<<it->second<<endl;
return 0;
}
실행 결과
합이 0인 하위 배열은 1부터 1까지 합이 0인 하위 배열은 0부터 3까지 합이 0인 하위 배열은 3부터 4까지 합이 0인 하위 배열은 0부터 6까지 합이 0인 하위 배열은 4부터 6까지
결과 해석
프로그램은 조건을 만족하는 하위 배열의 시작 인덱스와 끝 인덱스를 쌍(pair)으로 저장한 뒤 한꺼번에 출력합니다. 위 결과의 각 구간에 해당하는 실제 요소들은 다음과 같습니다.
- [1, 1] → {0}
- [0, 3] → {-5, 0, 2, 3}
- [3, 4] → {3, -3}
- [0, 6] → {-5, 0, 2, 3, -3, 4, -1} (배열 전체)
- [4, 6] → {-3, 4, -1}
모든 구간의 요소 합이 실제로 0이 되는 것을 확인할 수 있습니다. 만약 조건을 만족하는 하위 배열이 하나도 없다면 "No subarray exists"(조건을 만족하는 하위 배열이 없음)라는 메시지가 출력됩니다.
복잡도 분석
- 완전 탐색: 시간 복잡도 O(n²), 공간 복잡도 O(1)
- 해싱 기반 풀이: 평균 시간 복잡도 O(n), 공간 복잡도 O(n)
해싱 방식은 배열을 한 번만 순회하면서 누적 합을 해시 테이블에 기록하므로, 입력 크기가 클 때 완전 탐색보다 훨씬 빠르게 동작합니다. 다만 출력해야 할 하위 배열의 개수 자체가 많아질 수 있으므로, 결과 저장에 필요한 공간은 구간의 수에 비례한다는 점을 참고하세요.