0과 1이 섞여 있는 배열에서 두 숫자의 개수가 동일한 가장 긴 연속 부분 배열을 찾는 문제는 코딩 테스트와 알고리즘 학습에서 자주 등장하는 유형입니다. 단순히 모든 구간을 확인하는 브루트 포스 방식은 O(n²) 이상의 시간이 걸리지만, 누적 합(Prefix Sum)과 해시 맵을 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다.
핵심 아이디어
이 문제의 핵심은 다음과 같습니다.
- 배열의 모든 0을 -1로 변환하면, 0과 1의 개수가 같은 구간의 합은 반드시 0이 됩니다.
- 따라서 누적 합이 같은 두 지점 사이의 구간은 항상 합이 0인 구간, 즉 0과 1의 개수가 같은 구간입니다.
- 각 누적 합 값이 처음 등장한 인덱스를 해시 맵에 저장해 두면, 같은 값이 다시 나타났을 때 두 인덱스의 차이로 부분 배열의 길이를 바로 계산할 수 있습니다.
알고리즘 단계
프로그램을 완성하기 위한 단계를 살펴보겠습니다.
- 배열을 초기화합니다.
- 배열 내 모든 0을 -1로 변환합니다.
- 이전 인덱스를 저장할 빈 해시 맵을 준비합니다.
- 합(sum)은 0, 최대 길이(maxLength)는 0, 끝 인덱스(endingIndex)는 -1로 초기화합니다.
- n번 반복하는 루프를 작성합니다.
- 현재 요소를 sum에 더합니다.
- sum이 0이라면 처음부터 현재 위치까지 전체 구간이 조건을 만족하므로, maxLength를 i + 1로, endingIndex를 i로 갱신합니다.
- sum이 해시 맵에 이미 존재하고, i - previousIndexes[sum]이 maxLength보다 크다면 maxLength와 endingIndex를 갱신합니다.
- 그렇지 않으면 현재 sum과 인덱스 i를 해시 맵에 저장합니다.
- 시작 인덱스(endingIndex - maxLength + 1)와 끝 인덱스(endingIndex)를 출력합니다.
예제 코드
위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
void findTheSubArray(int arr[], int n) {
unordered_map<int, int> previousIndexes;
int sum = 0, maxLength = 0, endingIndex = -1;
// 0을 -1로 변환
for (int i = 0; i < n; i++) {
arr[i] = arr[i] == 0 ? -1 : 1;
}
for (int i = 0; i < n; i++) {
sum += arr[i];
if (sum == 0) {
maxLength = i + 1;
endingIndex = i;
}
if (previousIndexes.find(sum) != previousIndexes.end()) {
if (maxLength < i - previousIndexes[sum]) {
maxLength = i - previousIndexes[sum];
endingIndex = i;
}
} else {
previousIndexes[sum] = i;
}
}
cout << endingIndex - maxLength + 1 << " " << endingIndex << endl;
}
int main() {
int arr[] = { 1, 1, 0, 0, 0, 1, 1, 1, 0 };
findTheSubArray(arr, 9);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
1 8
입력 배열 {1, 1, 0, 0, 0, 1, 1, 1, 0}에서 인덱스 1부터 8까지의 구간 {1, 0, 0, 0, 1, 1, 1, 0}은 1이 네 개, 0이 네 개로 개수가 같으며, 이것이 조건을 만족하는 가장 긴 부분 배열입니다.
마무리
이처럼 0을 -1로 치환하고 누적 합과 해시 맵을 결합하면 선형 시간 안에 문제를 해결할 수 있습니다. 이 기법은 '합이 k인 가장 긴 부분 배열' 등 다양한 변형 문제에도 응용되므로 꼭 익혀두시길 추천합니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.