다음 큰 요소란 무엇인가?
다음 큰 요소(Next Greater Element)란 배열에서 현재 요소의 오른쪽에 있는 값들 중, 처음으로 현재 요소보다 큰 값을 가지는 요소를 의미합니다. 만약 오른쪽에 더 큰 요소가 존재하지 않는다면 -1로 표시합니다.
간단한 예제를 통해 살펴보겠습니다.
arr = [4, 5, 3, 2, 1]
위 배열에서 4의 다음 큰 요소는 바로 옆에 있는 5입니다. 반면 3, 2, 1은 뒤에 자신보다 큰 요소가 없으므로 각각 -1이 됩니다.
알고리즘
이 문제는 스택(Stack)을 활용하면 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
배열을 임의의 숫자로 초기화합니다.
스택과 결과를 저장할 배열을 준비합니다.
배열의 끝(오른쪽)부터 왼쪽 방향으로 순회합니다.
스택이 비어 있지 않고, 스택의 top이 현재 요소보다 작거나 같은 동안 계속 pop 합니다.
스택이 비어 있다면 다음 큰 요소가 없다는 의미이므로 결과 배열에 -1을 저장합니다.
스택이 비어 있지 않다면 top 값이 곧 현재 요소의 다음 큰 요소이므로 결과 배열에 저장합니다.
현재 요소를 스택에 push 합니다.
순회가 끝나면 결과 배열을 탐색하면서 각 요소와 그에 해당하는 다음 큰 요소를 함께 출력합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
void nextGreaterElements(int arr[], int n) {
stack<int> s;
int result[n];
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && s.top() <= arr[i]) {
s.pop();
}
if (s.empty()) {
result[i] = -1;
}else {
result[i] = s.top();
}
s.push(arr[i]);
}
for (int i = 0; i < n; i++) {
cout << arr[i] << " -> " << result[i] << endl;
}
}
int main() {
int arr[] = { 1, 2, 3, 4, 5 };
int n = 5;
nextGreaterElements(arr, n);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 확인할 수 있습니다.
1 -> 2 2 -> 3 3 -> 4 4 -> 5 5 -> -1
복잡도 분석
배열을 한 번만 순회하고, 각 요소는 최대 한 번 push 되고 한 번 pop 되므로 전체 시간 복잡도는 O(n)입니다. 또한 스택과 결과 배열을 사용하기 때문에 공간 복잡도 역시 O(n)입니다. 이는 모든 요소 쌍을 비교하는 단순한 이중 반복문 방식(O(n²))보다 훨씬 효율적입니다.