C++ 배열에서 abs(i - j) × min(arr[i], arr[j])의 최댓값 구하기

이 문제에서는 N개의 정수로 이루어진 배열 arr[]가 주어집니다. 우리의 과제는 배열 arr[]에서 abs(i - j) × min(arr[i], arr[j])의 최댓값을 찾는 것입니다.

문제 설명

두 요소 값 중 작은 값과, 그 두 요소의 인덱스 차이의 절댓값을 곱한 값이 가장 커지는 경우를 찾아야 합니다. 즉, 임의의 두 인덱스 i와 j에 대해 abs(i - j) × min(arr[i], arr[j]) 값을 최대화해야 합니다.

입력 예시

arr[] = {5, 7, 3, 6, 4}

출력 예시

16

설명

최댓값은 인덱스 0과 4 사이에서 얻을 수 있습니다.
=> abs(0 - 4) * min(arr[0], arr[4])
=> 4 * min(5, 4) => 4 * 4 = 16

해결 접근 방법

방법 1: 중첩 반복문 (브루트 포스)

가장 단순한 해결 방법은 중첩 반복문을 사용하는 것입니다. 두 개의 반복문으로 모든 인덱스 쌍 (i, j)에 대해 해당 값을 계산하고, 그중 최댓값을 반환하면 됩니다.

이 방법은 이해하기 쉽지만 시간 복잡도가 O(n²)이므로 배열의 크기가 커지면 비효율적입니다.

방법 2: 두 포인터(Two Pointer) 기법

더 효율적인 해결 방법은 두 개의 포인터를 사용하는 것입니다. 하나는 배열의 시작점에서, 다른 하나는 끝점에서 출발합니다.

각 단계에서 두 포인터가 가리키는 값으로 필요한 곱을 계산하여 maxVal 변수에 저장된 최댓값과 비교합니다. 그다음, 더 작은 값을 가진 쪽의 포인터를 안쪽으로 이동시킵니다. 이는 더 작은 값을 유지한 채 거리를 줄이는 것이 항상 손해이기 때문입니다. 두 포인터가 서로 교차할 때까지 이 과정을 반복하고, 마지막에 maxVal을 반환합니다.

이 방법의 시간 복잡도는 O(n)으로 훨씬 효율적입니다.

솔루션 동작 예시 프로그램

#include<iostream>
using namespace std;

int calcMaxProdValue(int arr[], int n) {
    int maxVal = -100;
    int currentVal;
    int start = 0, end = n - 1;
    
    while (start < end) {
        if (arr[start] < arr[end]) {
            currentVal = arr[start] * (end - start);
            start++;
        }
        else {
            currentVal = arr[end] * (end - start);
            end--;
        }
        maxVal = max(maxVal, currentVal);
    }
    return maxVal;
}

int main() {
    int arr[] = {5, 7, 3, 6, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "배열에서 abs(i - j) * min(arr[i], arr[j])의 최댓값은 "
         << calcMaxProdValue(arr, n);
    return 0;
}

출력 결과

배열에서 abs(i - j) * min(arr[i], arr[j])의 최댓값은 16

마무리

이 문제는 울타리 사이에 담을 수 있는 물의 최대량을 구하는 '물통(Container With Most Water)' 문제와 유사한 패턴입니다. 두 포인터 기법을 활용하면 O(n²)의 브루트 포스 방식 대신 O(n)의 선형 시간 안에 최적해를 구할 수 있다는 점이 핵심입니다.