C++ 최대 삭제 값(Maximum Erasure Value) 문제 풀이

문제 소개

양의 정수로 이루어진 배열이 주어졌을 때, 모든 요소가 중복 없이 고유한(unique) 부분 배열을 하나 선택해 제거하는 문제입니다. 이때 얻는 점수는 해당 부분 배열에 포함된 요소들의 합과 같으며, 정확히 하나의 부분 배열만 제거할 때 얻을 수 있는 최대 점수를 구하는 것이 목표입니다.

여기서 배열 arr이 배열 a의 부분 배열(subarray)이라는 것은, a의 연속된 일부분, 즉 임의의 인덱스 (l, r)에 대해 a[l], a[l+1], ..., a[r]과 동일함을 의미합니다.

예제 1

arr[ ] = { 1,2,4,5,6 }

출력:

설명: 최적의 부분 배열은 {2,4,5,6}이며, 그 합은 17입니다.

예제 2

arr[ ] = {5,3,1,3,5,3,1,3,5}

출력:

설명: 최적의 부분 배열은 {5,3,1} 또는 {1,3,5}이며, 두 경우 모두 합이 9입니다.

문제 해결 접근법: 슬라이딩 윈도우

이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 이 기법은 중첩 반복문을 하나의 반복문으로 변환해 시간 복잡도를 O(n) 수준까지 낮출 수 있는 강력한 도구입니다.

먼저 왼쪽 포인터(i), 오른쪽 포인터(j), 그리고 윈도우 내 요소의 합을 저장할 변수 'win'을 초기화합니다. 배열을 순회하면서 각 시점의 윈도우 합이 지금까지의 최대값인지 확인하고, 순회가 끝나면 그 최대값을 결과로 반환합니다.

단계별 풀이 과정

양의 정수 배열을 입력으로 받습니다.
maximumUniqueSubarray(vector<int>& arr) 함수가 배열을 매개변수로 받아 처리합니다.
포인터 i, j와 윈도우 합 win을 선언한 뒤 배열을 순회합니다. 현재 탐색 중인 요소(arr[j])가 이미 HashSet에 존재한다면, 중복이 사라질 때까지 왼쪽 끝 요소를 HashSet에서 제거하고 win에서 그 값을 빼면서 i를 앞으로 이동시킵니다.
중복이 없다면 해당 요소를 HashSet에 추가하고 win에 더한 후, result와 win 중 더 큰 값을 result에 저장합니다.
순회가 끝나면 result를 반환합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
int maximumUniqueSubarray(vector<int>& arr) {
    int result = 0;
    unordered_set<int> hashset;
    for (int i = 0, j = 0, win = 0; j < arr.size(); j++) {
        while (hashset.find(arr[j]) != hashset.end()) {
            hashset.erase(arr[i]);
            win -= arr[i];
            i++;
        }
        hashset.insert(arr[j]);
        win += arr[j];
        result = max(result, win);
    }
    return result;
}
int main(){
    vector<int>nums = {5,3,1,3,5,3,1,3,5};
    cout<<maximumUniqueSubarray(nums)<<endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.