C++로 구현하는 왼쪽·오른쪽 '다음 큰 요소' 인덱스 곱의 최댓값 알고리즘

이 글에서는 배열 arr[]가 주어졌을 때, 각 원소를 기준으로 왼쪽과 오른쪽에 존재하는 '다음 큰 요소(next greater element)'의 인덱스를 구하고, 두 인덱스의 곱(left[i] × right[i]) 중 최댓값을 계산하는 프로그램을 작성하는 방법을 알아봅니다.

문제 설명

주어진 배열에 대해 left[i] × right[i] 값의 최댓값을 구해야 합니다. 두 배열은 다음과 같이 정의됩니다.

left[i] = j (단, arr[i] < arr[j] 이고 i > j)
right[i] = j (단, arr[i] < arr[j] 이고 i < j)
* 배열은 1부터 시작하는 인덱스를 사용합니다.

예시로 이해하기

입력

arr[6] = {5, 2, 3, 1, 8, 6}

출력

15

풀이 과정

먼저 각 원소의 왼쪽·오른쪽 다음 큰 요소의 인덱스를 담은 배열을 만들면 다음과 같습니다.

left[]  = {0, 1, 1, 3, 0, 5}
right[] = {5, 3, 5, 5, 0, 0}

각 인덱스별로 두 값의 곱을 계산하면:

인덱스 1 → 0 × 5 = 0
인덱스 2 → 1 × 3 = 3
인덱스 3 → 1 × 5 = 5
인덱스 4 → 3 × 5 = 15
인덱스 5 → 0 × 0 = 0
인덱스 6 → 0 × 5 = 0

따라서 최대 곱은 15입니다.

접근 방법

각 원소의 왼쪽과 오른쪽에 있는 더 큰 요소의 인덱스를 먼저 구한 뒤, 두 인덱스의 곱을 저장하고 서로 비교하여 최댓값을 찾습니다.

모든 원소에 대해 왼쪽·오른쪽의 가장 가까운 큰 요소를 효율적으로 찾으려면 스택(stack)을 활용하는 것이 좋습니다. 스택에는 아직 '다음 큰 요소'를 찾지 못한 인덱스가 쌓이며, 다음 규칙에 따라 동작합니다.

① 스택이 비어 있으면 → 현재 인덱스를 push
② 현재 값 arr[i]가 스택 top이 가리키는 값보다 크면 → top을 pop하고, 해당 인덱스의 답을 i+1로 기록

이 과정을 배열을 한 번만 순회하며 수행하면 모든 원소의 다음 큰 요소 인덱스를 선형 시간에 구할 수 있습니다. 왼쪽 방향의 경우 배열을 뒤에서 앞으로 순회하면 같은 방식으로 처리할 수 있습니다.

C++ 구현 예제

위 접근 방식을 구현한 전체 코드입니다.

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

// ch == 'L' : 왼쪽 방향, ch == 'R' : 오른쪽 방향의 다음 큰 요소 인덱스를 찾음
int* findNextGreaterIndex(int a[], int n, char ch) {
    int* greaterIndex = new int[n];
    stack<int> st;
    if (ch == 'R') {
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && a[i] > a[st.top() - 1]) {
                int idx = st.top();
                st.pop();
                greaterIndex[idx - 1] = i + 1;
            }
            st.push(i + 1);
        }
    } else { // 'L'
        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && a[i] > a[st.top() - 1]) {
                int idx = st.top();
                st.pop();
                greaterIndex[idx - 1] = i + 1;
            }
            st.push(i + 1);
        }
    }
    return greaterIndex;
}

int calcMaxGreaterIndexProd(int arr[], int n) {
    int* left = findNextGreaterIndex(arr, n, 'L');
    int* right = findNextGreaterIndex(arr, n, 'R');
    int maxProd = 0;
    for (int i = 0; i < n; i++) {
        maxProd = max(maxProd, left[i] * right[i]);
    }
    return maxProd;
}

int main() {
    int arr[] = {5, 2, 3, 1, 8, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "왼쪽과 오른쪽 다음 큰 요소 인덱스 곱의 최댓값은 "
         << calcMaxGreaterIndexProd(arr, n) << endl;
    return 0;
}

실행 결과

왼쪽과 오른쪽 다음 큰 요소 인덱스 곱의 최댓값은 15

복잡도 분석

스택 기반 접근법에서 각 인덱스는 최대 한 번 push되고 한 번 pop되므로, 시간 복잡도는 O(n)입니다. 또한 왼쪽·오른쪽 결과 배열과 스택을 저장해야 하므로 공간 복잡도 역시 O(n)입니다. 단순히 매 원소마다 양방향을 일일이 탐색하는 O(n²) 완전 탐색보다 훨씬 효율적이라는 점이 이 방법의 핵심 장점입니다.