문제 개요
이 문제에서는 하나의 배열이 주어지며, 우리의 과제는 배열에서 현재 요소보다 앞쪽(왼쪽)에 위치하면서 더 큰 값을 찾아 출력하는 것입니다. 만약 그런 요소가 존재하지 않는다면 -1을 출력해야 합니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력: {6, 2, 7, 1, 5, 3}
출력: -1, 6, -1, 7, 7, 7각 요소별 결과를 분석하면 다음과 같습니다.
- 6: 배열의 첫 번째 요소이므로 앞에 비교할 요소가 없음 → -1
- 2: 앞쪽에서 더 큰 요소는 6 → 6
- 7: 앞쪽에 더 큰 요소가 없음 → -1
- 1: 앞쪽에서 가장 먼저 만나는 더 큰 요소는 7 → 7
- 5: 앞쪽에서 더 큰 요소는 7 → 7
- 3: 앞쪽에서 더 큰 요소는 7 → 7
방법 1: 중첩 반복문(Nested Loop) 사용
가장 직관적인 해결 방법은 중첩 반복문을 활용하는 것입니다. 외부 반복문으로 각 요소를 순회하고, 내부 반복문으로 해당 요소의 앞쪽 구간을 역순으로 탐색하며 더 큰 요소를 찾습니다.
시간 복잡도: O(n²) / 공간 복잡도: O(1)
#include <iostream>
using namespace std;
void precedingGreatestElement(int arr[], int n){
cout << "-1\t";
int i, j;
for (i = 1; i < n; i++) {
for (j = i-1; j >= 0; j--) {
if (arr[i] < arr[j]) {
cout << arr[j] << "\t";
break;
}
}
if (j == -1)
cout << "-1\t";
}
}
int main() {
int arr[] = { 6, 2, 7, 1, 12, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
precedingGreatestElement(arr, n);
return 0;
}출력
-1 6 -1 7 -1 12
이 방식은 구현이 간단하지만, 배열의 길이가 커질수록 이중 반복문 때문에 연산량이 제곱으로 증가한다는 단점이 있습니다.
방법 2: 스택(Stack) 자료구조 활용
훨씬 효율적인 접근 방식은 스택 자료구조를 사용하는 것입니다. 핵심 아이디어는 스택의 최상단(top)에 항상 현재 요소 앞쪽의 '더 큰 요소' 후보를 유지하는 것입니다.
동작 원리는 다음과 같습니다.
- 새로운 요소를 처리하기 전에, 스택의 top이 현재 요소보다 작으면 계속 pop하여 제거합니다.
- 스택이 비어 있다면 앞쪽에 더 큰 요소가 없다는 의미이므로 -1을 출력합니다.
- 스택이 비어 있지 않다면 top 값을 출력합니다.
- 마지막으로 현재 요소를 스택에 push합니다.
시간 복잡도: O(n) / 공간 복잡도: O(n)
#include <bits/stdc++.h>
using namespace std;
void precedingGreatestElement(int arr[], int n) {
stack<int> elements;
elements.push(arr[0]);
cout << "-1\t";
for (int i = 1; i < n; i++) {
while (elements.empty() == false && elements.top() < arr[i])
elements.pop();
if(elements.empty())
cout << "-1\t";
else
cout << elements.top() << "\t";
elements.push(arr[i]);
}
}
int main() {
int arr[] = { 6, 2, 7, 1, 12, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
precedingGreatestElement(arr, n);
return 0;
}출력
-1 6 -1 7 -1 12
정리
두 방식 모두 동일한 결과를 출력하지만, 스택 기반 접근 방식은 선형 시간(O(n))에 실행되므로 대규모 데이터에서 훨씬 뛰어난 성능을 보여줍니다. 이 패턴은 '다음 더 큰 요소(Next Greater Element)'와 같은 유사한 배열 문제에도 그대로 응용할 수 있으므로, 코딩 테스트 준비를 위해 꼭 익혀두는 것이 좋습니다.