C++로 배열에서 '다음 큰 요소의 다음 작은 요소' 찾기

문제 이해하기

이 문제에서는 n개의 정수로 이루어진 배열 arr[]가 주어집니다. 목표는 배열에서 '다음 큰 요소(next greater)의 다음 작은 요소(next smaller)'를 찾는 것입니다.

즉, 각 요소에 대해 먼저 오른쪽에 있는 요소 중 현재 요소보다 처음으로 큰 요소(다음 큰 요소)를 찾고, 이어서 그 큰 요소를 기준으로 다시 오른쪽에 있는 요소 중 처음으로 작은 요소(다음 작은 요소)를 찾아야 합니다. 만약 다음 큰 요소 또는 다음 작은 요소가 존재하지 않는다면 -1을 반환합니다.

입력 · 출력 예시

입력

arr[] = {4, 2, 8, 3, 9, 1}

출력

{3, 3, 1, 1, -1, -1}

예시 설명

먼저 각 요소의 다음 큰 요소 배열을 구하면 {8, 8, 9, 9, -1, -1}입니다. 9는 배열의 최댓값이고 1은 마지막 요소이므로 이 둘은 다음 큰 요소를 가지지 않습니다.

이제 각 다음 큰 요소의 다음 작은 요소를 구하면 최종 결과는 {3, 3, 1, 1, -1, -1}이 됩니다.

해결 접근 방법

1. 단순한 접근 (브루트 포스)

가장 직관적인 방법은 배열을 순회하면서 각 요소마다 다음 작업을 수행하는 것입니다.

현재 요소보다 큰 첫 번째 요소(다음 큰 요소)를 배열에서 찾습니다.
남은 배열에서 그 큰 요소보다 작은 첫 번째 요소를 찾습니다.

이 방법은 동작하지만 중첩 반복문을 사용하기 때문에 시간 복잡도가 O(n²)으로 비효율적입니다.

2. 스택을 활용한 효율적인 접근

더 나은 해결책은 스택(stack) 자료구조와 요소의 인덱스를 함께 활용하는 것입니다.

nextGreater[]와 nextSmaller[]라는 두 개의 배열에 각각 '다음 큰 요소의 인덱스'와 '다음 작은 요소의 인덱스'를 저장합니다. 예를 들어 nextGreater[i]에는 arr[i]의 다음 큰 요소의 인덱스가 저장되므로 실제 값은 arr[nextGreater[i]]가 됩니다. nextSmaller[]도 동일한 방식으로 동작합니다.

이렇게 인덱스를 관리하면 원하는 답, 즉 '다음 큰 요소의 다음 작은 요소'는 nextGreater[i] 위치의 다음 작은 요소를 찾는 것으로 구할 수 있습니다. 따라서 최종 정답 요소는 arr[nextSmaller[nextGreater[i]]]가 됩니다.

다음 큰 요소 찾기 알고리즘

배열을 뒤에서 앞으로 순회합니다(i = n-1 → 0).
스택이 비어 있지 않고 스택 top이 가리키는 값이 현재 요소보다 작거나 같으면 pop합니다. 더 큰 요소를 찾거나 스택이 빌 때까지 반복합니다.
스택이 비어 있다면 → 다음 큰 요소가 없으므로 nextGreater[i] = -1을 저장합니다.
그렇지 않다면 → 다음 큰 요소는 스택 top에 있으므로 nextGreater[i] = stack.top()을 저장합니다.
현재 요소의 인덱스를 스택에 push합니다.

동일한 방법에서 비교 조건만 반대로 바꾸면 다음 작은 요소도 찾을 수 있습니다. 두 인덱스 배열을 모두 구한 뒤 이를 조합하면 각 위치의 최종 답을 손쉽게 얻을 수 있습니다.

C++ 구현 코드

#include<bits/stdc++.h>
using namespace std;
void findNextGreater(int arr[], int n, int next[]) {
    stack<int> nextGreater;
    int i = n-1;
    while(i >= 0) {
        while (!nextGreater.empty() && arr[nextGreater.top()] <= arr[i])
            nextGreater.pop();
        if (!nextGreater.empty())
            next[i] = nextGreater.top();
        else
            next[i] = -1;
        nextGreater.push(i);
        i--;
    }
}
void findNextSmaller(int arr[], int n, int next[]) {
    stack<int> nextSmaller;
    int i = n-1;
    while(i >= 0){
        while (!nextSmaller.empty() && arr[nextSmaller.top()] >= arr[i])
            nextSmaller.pop();
        if (!nextSmaller.empty())
            next[i] = nextSmaller.top();
        else
            next[i] = -1;
        nextSmaller.push(i);
        i--;
    }
}
void findNextSmallerofNextGreaterElemenetArray(int arr[], int n) {
    int nextGreaterIndex[n];
    int nextSmallerIndex[n];
    findNextGreater(arr, n, nextGreaterIndex);
    findNextSmaller(arr, n, nextSmallerIndex);
    for (int i=0; i< n; i++){
        if (nextGreaterIndex[i] != -1 && nextSmallerIndex[nextGreaterIndex[i]] != -1)
            cout<<arr[nextSmallerIndex[nextGreaterIndex[i]]]<<"\t";
        else
            cout<<"-1"<<"\t";
    }
}
int main(){
    int arr[] = {4, 2, 8, 3, 9, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"All next smaller of next greater elements of the array are ";
    findNextSmallerofNextGreaterElemenetArray(arr, n);
    return 0;
}

실행 결과

All next smaller of next greater elements of the array are 3 3 1 1 -1 -1

복잡도 분석

스택 기반 접근에서는 각 요소가 최대 한 번 push되고 한 번 pop되므로 시간 복잡도는 O(n)입니다. 공간 복잡도는 두 개의 인덱스 배열과 스택을 위해 O(n)이 필요합니다. 브루트 포스 방식의 O(n²)에 비해 대규모 입력에서 훨씬 효율적입니다.