C++로 구현하는 '다음 작은 요소' 찾기 알고리즘

다음 작은 요소(Next Smaller Element)란 어떤 요소 뒤에서 처음으로 등장하는 더 작은 값을 의미합니다. 예시를 통해 살펴보겠습니다.

arr = [1, 2, 3, 5, 4]

위 배열에서 5의 다음 작은 요소는 바로 뒤에 있는 4입니다. 반면 1, 2, 3은 자신보다 작은 값이 뒤에 존재하지 않으므로 다음 작은 요소는 -1이 됩니다.

알고리즘

• 배열을 임의의 숫자로 초기화합니다.

• 스택을 하나 생성합니다.

• 배열의 첫 번째 요소를 스택에 넣습니다(push).

• 배열의 나머지 요소들을 순서대로 순회합니다.

  • 스택이 비어 있다면 현재 요소를 스택에 넣습니다.

  • 현재 요소가 스택 최상단(top) 요소보다 작은 동안 다음을 반복합니다.

    • 최상단 요소와 그 다음 작은 요소(현재 요소)를 출력합니다.

    • 최상단 요소를 제거(pop)합니다.

  • 현재 요소를 스택에 넣습니다.

• 순회가 끝난 후 스택이 빌 때까지 남아 있는 요소들을 출력합니다. 이 요소들의 다음 작은 요소는 -1입니다.

C++ 구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;
void nextSmallerElements(int arr[], int n) {
   stack<int> s;
   s.push(arr[0]);
   for (int i = 1; i < n; i++) {
      if (s.empty()) {
         s.push(arr[i]);
         continue;
      }
      while (!s.empty() && s.top() > arr[i]) {
         cout << s.top() << " -> " << arr[i] << endl;
         s.pop();
      }
      s.push(arr[i]);
   }
   while (!s.empty()) {
      cout << s.top() << " -> " << -1 << endl;
      s.pop();
   }
}
int main() {
   int arr[] = { 5, 4, 3, 2, 1 };
   int n = 5;
   nextSmallerElements(arr, n);
   return 0;
}

실행 결과

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

5 -> 4
4 -> 3
3 -> 2
2 -> 1
1 -> -1

동작 원리 및 복잡도

이 알고리즘은 스택을 활용해 한 번의 순회만으로 모든 요소의 다음 작은 요소를 찾습니다. 더 작은 값이 등장할 때마다 스택에 쌓여 있던 큰 값들이 차례로 처리되므로, 시간 복잡도는 O(n), 공간 복잡도 역시 최악의 경우 O(n)입니다. 감소 수열과 같은 입력에서 특히 효율적으로 동작하며, 배열 문제에서 자주 활용되는 대표적인 스택 응용 패턴 중 하나입니다.