C++에서 다른 배열의 동일 윈도우 요소가 고유할 때 배열 윈도우의 최대 합 구하기

이 튜토리얼에서는 한 배열의 윈도우(연속된 구간) 합이 최대가 되도록 하면서, 동일한 범위의 다른 배열 윈도우에 포함된 요소들이 모두 고유(중복 없음)하도록 만드는 프로그램을 다룹니다.

문제에서는 서로 같은 개수의 요소를 가진 두 개의 배열이 주어집니다. 우리의 목표는 한 배열에서 요소들의 합이 최대가 되는 윈도우를 찾되, 그 윈도우와 같은 범위에 있는 다른 배열의 요소들은 중복이 없어야 한다는 조건을 만족시키는 것입니다.

접근 방법

이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 해시 셋(unordered_set)을 활용하면 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

1. 배열을 왼쪽에서 오른쪽으로 순회하며 현재 요소를 윈도우에 추가합니다.
2. 현재 요소가 이미 윈도우 안에 존재한다면, 중복이 사라질 때까지 윈도우의 왼쪽 끝 요소를 하나씩 제거합니다.
3. 매 단계마다 윈도우에 포함된 요소들의 합을 계산하고, 지금까지의 최대값보다 크면 결과를 갱신합니다.

이 방식에서 각 요소는 최대 두 번(윈도우에 들어올 때와 나갈 때)만 처리되므로 전체 시간 복잡도는 O(n)입니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
//최대 합 윈도우 반환
int returnMaxSum(int A[], int B[], int n) {
   //요소를 집합에 저장하여 중복 검사
   unordered_set<int> mp;
   int result = 0;
   int curr_sum = 0, curr_begin = 0;
   for (int i = 0; i < n; ++i) {
      while (mp.find(A[i]) != mp.end()) {
         mp.erase(A[curr_begin]);
         curr_sum -= B[curr_begin];
         curr_begin++;
      }
      mp.insert(A[i]);
      curr_sum += B[i];
      result = max(result, curr_sum);
   }
   return result;
}
int main() {
   int A[] = { 0, 1, 2, 3, 0, 1, 4 };
   int B[] = { 9, 8, 1, 2, 3, 4, 5 };
   int n = sizeof(A)/sizeof(A[0]);
   cout << returnMaxSum(A, B, n);
   return 0;
}

출력

20

동작 과정 살펴보기

위 예제에서 배열 A = {0, 1, 2, 3, 0, 1, 4}, 배열 B = {9, 8, 1, 2, 3, 4, 5}입니다.

인덱스 0~3의 윈도우에서 A의 요소 {0, 1, 2, 3}은 모두 고유하며, 이때 B의 합은 9 + 8 + 1 + 2 = 20으로 최대가 됩니다. 반면 인덱스 3~6의 윈도우({3, 0, 1, 4}) 역시 요소가 고유하지만 합은 2 + 3 + 4 + 5 = 14로 더 작습니다. 따라서 정답은 20입니다.