C++로 왼쪽·오른쪽 다음 큰 요소 인덱스 곱의 최댓값 구하기

문제 개요

이 글에서는 정수 배열이 주어졌을 때, 왼쪽과 오른쪽에 있는 다음 큰 요소(next greater element)의 인덱스 곱 중 최댓값을 구하는 프로그램을 C++로 작성하는 방법을 알아보겠습니다.

각 요소 i에 대해 다음 두 값을 정의합니다.

• L(i): 현재 요소보다 크면서 왼쪽에서 가장 가까운 요소의 인덱스 (인덱스는 1부터 시작)
• R(i): 현재 요소보다 크면서 오른쪽에서 가장 가까운 요소의 인덱스

목표는 모든 요소에 대해 L(i) × R(i)를 계산한 뒤 그중 최댓값을 찾는 것입니다. 만약 어느 쪽에도 더 큰 요소가 존재하지 않으면 해당 방향의 값은 0으로 처리되어 곱 역시 0이 됩니다.

풀이 접근: 스택 활용

모든 요소마다 양쪽을 일일이 탐색하면 O(n²)의 시간이 필요하지만, 스택(stack)을 활용하면 각 방향별로 O(n) 만에 다음 큰 요소의 인덱스를 미리 계산할 수 있습니다.

1. nextGreaterInLeft: 배열을 오른쪽에서 왼쪽으로 순회하며 스택에 인덱스를 쌓고, 현재 값보다 작은 요소들을 꺼내면서 왼쪽 다음 큰 요소의 인덱스를 기록합니다.
2. nextGreaterInRight: 반대로 왼쪽에서 오른쪽으로 순회하며 동일한 원리로 오른쪽 다음 큰 요소의 인덱스를 구합니다.
3. LRProduct: 두 결과 배열의 값을 곱하여 전체 최댓값을 반환합니다.

C++ 구현 예제

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

// 왼쪽에 있는 다음 큰 요소의 인덱스 찾기
vector<int> nextGreaterInLeft(int a[], int n) {
    vector<int> left_index(MAX, 0);
    stack<int> s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && a[i] > a[s.top() - 1]) {
            int r = s.top();
            s.pop();
            left_index[r - 1] = i + 1;
        }
        s.push(i + 1);
    }
    return left_index;
}

// 오른쪽에 있는 다음 큰 요소의 인덱스 찾기
vector<int> nextGreaterInRight(int a[], int n) {
    vector<int> right_index(MAX, 0);
    stack<int> s;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && a[i] > a[s.top() - 1]) {
            int r = s.top();
            s.pop();
            right_index[r - 1] = i + 1;
        }
        s.push(i + 1);
    }
    return right_index;
}

// L × R 곱의 최댓값 계산
int LRProduct(int arr[], int n) {
    vector<int> left = nextGreaterInLeft(arr, n);
    vector<int> right = nextGreaterInRight(arr, n);
    int ans = -1;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, left[i] * right[i]);
    }
    return ans;
}

int main() {
    int arr[] = { 5, 4, 3, 4, 5 };
    int n = sizeof(arr) / sizeof(arr[1]);
    cout << LRProduct(arr, n);
    return 0;
}

실행 결과

8

결과 분석

배열 {5, 4, 3, 4, 5}에서 각 요소(1-based 인덱스)의 L × R 값은 다음과 같습니다.

양 끝의 요소(값 5)는 자신보다 큰 요소가 없으므로 곱이 0이 되고, 나머지 요소 중에서는 인덱스 3(값 3)의 곱 8이 가장 큽니다. 따라서 프로그램은 8을 출력합니다.

마무리

이처럼 스택을 활용하면 다음 큰 요소 유형의 문제를 선형 시간 O(n) 안에 해결할 수 있습니다. 이 기법은 히스토그램에서 가장 큰 직사각형 찾기, 주식 가격 변화 분석 등 다양한 배열 기반 문제에도 폭넓게 응용되므로 잘 익혀두면 큰 도움이 됩니다.