이진 배열(0과 1로만 구성된 배열)이 주어졌을 때, 0과 1의 개수가 같은 가장 긴 연속 부분 배열의 길이를 찾는 문제입니다. 예를 들어 입력이 [0,1,0]이라면 출력은 2가 됩니다. [0,1] 또는 [1,0]이 0과 1의 개수가 동일한 가장 긴 연속 배열이기 때문입니다.
해결 전략: 누적 합과 맵 활용
이 문제를 효율적으로 풀려면 누적 합(prefix sum)과 맵(map)을 함께 사용하는 것이 핵심입니다. 핵심 아이디어는 0을 -1로 취급하는 것입니다. 그렇게 하면 누적 합이 같은 두 지점 사이의 구간에는 반드시 0과 1의 개수가 동일하게 포함됩니다.
알고리즘의 구체적인 단계는 다음과 같습니다.
- ret := 0, n := nums의 크기, sum := 0으로 초기화합니다.
- 맵 m을 생성하고 m[0] := -1로 설정합니다. 이는 배열의 시작 위치를 의미하며, 처음부터 현재 위치까지의 구간도 올바르게 계산할 수 있게 해줍니다.
- i를 0부터 nums 크기 - 1까지 반복합니다.
- nums[i]가 1이면 sum에 1을 더하고, 그렇지 않으면 1을 뺍니다.
- sum이 이미 m에 존재하면 ret := max(ret, i - m[sum])으로 갱신하고, 존재하지 않으면 m[sum] := i로 저장합니다.
- ret을 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int ret = 0;
int n = nums.size();
int sum = 0;
map <int, int> m;
m[0] = -1;
for(int i = 0; i < nums.size(); i++){
sum += nums[i] == 1 ? 1: -1;
if(m.count(sum)){
ret = max(ret, i - m[sum]);
}else m[sum] = i;
}
return ret;
}
};
main(){
vector<int> v = {0,1,0,0,1};
Solution ob;
cout << (ob.findMaxLength(v));
}입력
[0,1,0,0,1]
출력
4
실행 과정 상세 분석
입력 [0,1,0,0,1]에 대해 알고리즘이 어떻게 동작하는지 단계별로 살펴보겠습니다.
- i = 0 (값 0): sum = -1 → 맵에 없으므로 m[-1] = 0 저장
- i = 1 (값 1): sum = 0 → m[0] = -1이 존재하므로 ret = max(0, 1-(-1)) = 2
- i = 2 (값 0): sum = -1 → m[-1] = 0이 존재하므로 ret = max(2, 2-0) = 2
- i = 3 (값 0): sum = -2 → 맵에 없으므로 m[-2] = 3 저장
- i = 4 (값 1): sum = -1 → m[-1] = 0이 존재하므로 ret = max(2, 4-0) = 4
최종 결과는 4이며, 이는 인덱스 1부터 4까지의 부분 배열 [1,0,0,1]에 해당합니다. 이 구간에는 0이 2개, 1이 2개로 개수가 정확히 같습니다.
시간 및 공간 복잡도
- 시간 복잡도: std::map을 사용하면 O(n log n), unordered_map을 사용하면 O(n)입니다.
- 공간 복잡도: 맵에 최대 n개의 항목이 저장될 수 있으므로 O(n)입니다.