원형 배열(circular array)이 있다고 가정해 봅시다. 여기서 '원형'이란 배열의 마지막 요소 다음에 다시 첫 번째 요소가 오는 구조를 의미합니다. 이러한 배열에서 모든 요소에 대해 다음 큰 수(Next Greater Number)를 찾아 출력해야 합니다.
여기서 어떤 수 x의 '다음 큰 수'란, 배열을 순회하는 방향으로 x 바로 다음에 처음 등장하는 더 큰 수를 말합니다. 원형 배열이므로 끝에 도달하면 다시 처음부터 탐색을 이어갈 수 있습니다. 만약 더 큰 수가 존재하지 않는다면 결과값은 -1이 됩니다.
예를 들어 입력 배열이 [1, 2, 1, 3, 2, 1]이라면 출력은 [2, 3, 3, -1, 3, 2]가 됩니다.
문제 해결 접근 방법
이 문제는 스택(Stack)을 활용한 단조 감소 스택 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 배열을 두 배 길이(2n)만큼 순회하면서, 스택에 쌓아둔 인덱스들 중 현재 값보다 작은 값들을 정리하는 것입니다. 알고리즘 단계는 다음과 같습니다.
- n := 배열의 크기
- 크기가 n인 배열 res를 선언하고 모든 값을 -1로 초기화한 뒤, 스택 st를 하나 정의합니다.
- i를 0부터 2n까지 반복합니다.
- index := i mod n, x := nums[index]
- 스택이 비어 있지 않고 nums[스택 최상단] < x인 동안 다음을 반복합니다.
- res[스택 최상단] := x
- 스택에서 최상단 요소를 제거합니다.
- index를 스택에 삽입합니다.
- res를 반환합니다.
왜 2n번 순회할까요?
원형 배열의 특성상 마지막 요소의 다음 큰 수는 배열 앞쪽에 있을 수 있습니다. 따라서 배열을 한 번 더 순회함으로써 모든 요소가 자신의 다음 큰 수를 만날 기회를 갖게 됩니다. 인덱스는 i % n 연산으로 실제 배열 범위 내에 유지됩니다.
C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector <int> res(n, - 1);
stack <int> st;
for(int i = 0; i < 2 * n; i++){
int idx = i % n;
int x = nums[idx];
while(!st.empty() && nums[st.top()] < x){
res[st.top()] = x;
st.pop();
}
st.push(idx);
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,3,2,1};
print_vector(ob.nextGreaterElements(v));
}입력
[1,2,1,3,2,1]
출력
[2,3,3,-1,3,2]
동작 원리 살펴보기
위 코드의 실행 흐름을 간단히 분석해 보면 다음과 같습니다.
- 배열 [1, 2, 1, 3, 2, 1]을 두 번 순회하며 각 위치의 값을 확인합니다.
- 현재 값 x가 스택에 저장된 인덱스의 값보다 크면, 해당 인덱스의 다음 큰 수는 x가 되므로 res 배열에 기록하고 스택에서 제거합니다.
- 예를 들어 인덱스 0의 값 1은 이후 등장하는 2보다 작으므로 res[0] = 2가 됩니다.
- 값 3은 그보다 작은 모든 선행 요소들의 다음 큰 수가 되어 res의 해당 위치들이 3으로 갱신됩니다.
- 마지막까지 갱신되지 않은 위치는 -1로 남습니다. 위 예제에서는 인덱스 3의 값 3이 해당됩니다.
이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로, 브루트 포스 방식(O(n²))에 비해 상당히 효율적입니다.