C++로 특정 요소를 제외한 최대 부분 배열 합 구하는 방법

이 문제에서는 크기가 n인 배열 arr1[]과 크기가 m인 배열 arr2[] 두 개가 주어집니다. 우리의 목표는 특정 요소들을 제외한 상태에서 최대 부분 배열 합(maximum subarray sum)을 구하는 프로그램을 작성하는 것입니다.

문제 설명 — 배열 arr1[]의 요소들 중 arr2[]에 존재하지 않는 값들만 사용하여 만들 수 있는 부분 배열(subarray) 중 합이 가장 큰 값을 찾아야 합니다.

예제로 이해하기

입력

arr1[] = {4, 5, 7, 2, 9}, arr2[] = {1, 9, 2, 7}

출력

9

설명

arr2[]에 포함된 요소(7, 2, 9)를 arr1[]에서 제거하면 {4, 5}만 남습니다.
두 요소는 연속된 하나의 부분 배열을 이루므로 합 = 4 + 5 = 9입니다.

해결 접근 방법

이 문제를 해결하는 기본적인 방법은 카데인 알고리즘(Kadane's Algorithm)을 활용하는 것입니다. 카데인 알고리즘은 배열에서 양수로 이루어진 연속 시퀀스를 효율적으로 찾아낼 수 있으며, 각 부분 배열의 합을 계산한 뒤 그중 최댓값을 반환합니다.

여기에 한 가지 수정을 더합니다. 최대 부분 배열을 계산할 때 arr2[]에 포함된 요소는 고려할 필요가 없다는 점입니다. 따라서 탐색 알고리즘을 통해 현재 요소가 arr2[]에 있는지 확인하고, 존재한다면 현재 윈도우(누적 합)를 초기화합니다. 매 단계마다 sum과 maxSum을 비교하여 maxSum = sum으로 갱신해 주면 됩니다.

구현 예제 1 — 이진 탐색 활용

#include <iostream>
using namespace std;

int isInArr2(int arr2[], int start, int end, int searchEle){
    if (end >= start) {
        int mid = start + (end − start) / 2;
        if (arr2[mid] == searchEle)
            return true;
        if (arr2[mid] > searchEle)
            return isInArr2(arr2, start, mid − 1, searchEle);
        return isInArr2(arr2, mid + 1, end, searchEle);
    }
    return false;
}

int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m){
    int maxSum = −1, sum = 0;
    for (int i = 0; i < n; i++) {
        if (isInArr2(arr2, 0, m, arr1[i])) {
            sum = 0;
            continue;
        }
        sum = max(arr1[i], sum + arr1[i]);
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

int main(){
    int arr1[] = { 5, 4, 7, 2, 9 };
    int arr2[] = { 1, 9, 2, 7 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);
    cout<<"특정 요소를 제외한 최대 부분 배열 합은 "
       <<calcMaxSubArraySum(arr1, arr2, n, m);
    return 0;
}

출력

특정 요소를 제외한 최대 부분 배열 합은 9

이 방법도 충분히 효과적이지만, 두 번째 배열에 요소가 존재하는지 확인하는 과정을 더 최적화하면 연산 시간을 줄일 수 있습니다.

개선된 접근 방법 — 해시 맵 활용

이진 탐색 대신 unordered_map을 사용하면 요소 존재 여부를 평균 O(1) 시간 복잡도로 확인할 수 있어 전체 성능이 향상됩니다. 먼저 arr2[]의 모든 요소를 해시 맵에 저장해 둔 뒤, 수정된 카데인 알고리즘을 순회하면서 각 요소가 맵에 있는지 빠르게 검사하는 방식입니다.

구현 예제 2 — unordered_map 활용

#include <bits/stdc++.h>
using namespace std;

int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m){
    unordered_map<int,int> checkVal;
    for(int i = 0; i < m; i++)
        checkVal[arr2[i]] = 1;

    int maxSum = −1, sum = 0;
    for (int i = 0; i < n; i++) {
        if (checkVal[arr1[i]] == 1) {
            sum = 0;
            continue;
        }
        sum = max(arr1[i], sum + arr1[i]);
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

int main(){
    int arr1[] = { 5, 4, 7, 2, 9 };
    int arr2[] = { 1, 9, 2, 7 };
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int m = sizeof(arr2) / sizeof(arr2[0]);
    cout<<"특정 요소를 제외한 최대 부분 배열 합은 "
       <<calcMaxSubArraySum(arr1, arr2, n, m);
    return 0;
}

출력

특정 요소를 제외한 최대 부분 배열 합은 9

마무리 정리

두 가지 접근법 모두 카데인 알고리즘을 기반으로 하지만, 제외 대상 요소를 확인하는 자료구조가 다릅니다. 이진 탐색은 O(m log n) 수준의 조회 비용이 드는 반면, unordered_map을 사용하면 평균적으로 O(n + m)의 시간 복잡도로 문제를 해결할 수 있습니다. 따라서 입력 크기가 커질수록 해시 맵 기반 접근이 더 유리하며, 실전 코딩 테스트에서도 널리 권장되는 방식입니다.