최대 스택(Maximum Stack)이란?
최대 스택은 일반적인 스택 기능에 더해, 현재 스택에 들어 있는 값들 중 최댓값을 빠르게 조회하거나 제거할 수 있는 자료구조입니다. 이번 글에서는 다음과 같은 연산을 지원하는 최대 스택을 C++로 구현해 보겠습니다.
- MaxStk() – 최대 스택의 새 인스턴스를 생성합니다.
- push(val) – val 값을 스택에 삽입합니다.
- top() – 스택의 가장 위(top)에 있는 요소를 반환합니다.
- max() – 스택에 있는 요소 중 최댓값을 반환합니다.
- pop() – 스택의 가장 위에 있는 요소를 제거하고 반환합니다.
- popmax() – 스택에서 최댓값을 제거하고 반환합니다.
동작 예시
MaxStk()로 최대 스택 객체를 생성한 뒤, 5, 15, 10 세 값을 차례로 push하고, 이어서 top(), max(), popmax(), max(), pop(), top()을 순서대로 호출한다고 가정해 보겠습니다. 초기 스택 상태는 [5, 15, 10]이며, 각 함수 호출에 대한 출력은 다음과 같습니다.
10, 15, 15, 10, 10, 5
풀이 접근 방법
핵심 아이디어는 두 개의 set(정렬된 집합)을 사용하는 것입니다. 하나는 스택 순서를 관리하는 stk, 다른 하나는 값 기준으로 정렬되는 aux입니다. 전체 흐름은 다음과 같습니다.
- pos_index := 0 으로 초기화합니다.
- set 컨테이너 두 개(stk, aux)를 정의합니다.
- 생성자는 특별한 작업 없이 비워 둡니다.
push(val)
- stk에 (pos_index, val) 쌍을 삽입합니다.
- aux에 (val, pos_index) 쌍을 삽입합니다.
- pos_index를 1 증가시킵니다.
top()
- stk가 비어 있으면 -1을 반환합니다.
- stk의 첫 번째 원소(가장 큰 인덱스)의 두 번째 값(val)을 반환합니다.
max()
- aux가 비어 있으면 -1을 반환합니다.
- aux의 첫 번째 원소의 첫 번째 값(최댓값)을 반환합니다.
pop()
- stk가 비어 있으면 -1을 반환합니다.
- id := stk 첫 번째 원소의 첫 번째 값, ret := 두 번째 값을 저장합니다.
- stk에서 첫 번째 원소를 삭제합니다.
- aux에서 (ret, id) 쌍을 삭제합니다.
- ret을 반환합니다.
popmax()
- aux가 비어 있으면 -1을 반환합니다.
- ret := aux 첫 번째 원소의 첫 번째 값, id := 두 번째 값을 저장합니다.
- aux에서 첫 번째 원소를 삭제합니다.
- stk에서 (id, ret) 쌍을 삭제합니다.
- ret을 반환합니다.
여기서 greater<> 비교자를 사용해 내림차순으로 정렬하기 때문에, set의 begin()은 항상 "가장 큰 키"를 가리킵니다. stk는 인덱스(pos_index)를 키로 사용하므로 begin()이 곧 스택의 top이 되고, aux는 값(val)을 키로 사용하므로 begin()이 곧 최댓값이 됩니다. 덕분에 모든 연산을 O(log n) 시간에 처리할 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class MaxStk {
int pos_index = 0;
set<pair<int, int>, greater<>> stk, aux;
public:
MaxStk() {}
void push(int val) {
stk.emplace(pos_index, val);
aux.emplace(val, pos_index);
pos_index++;
}
int top() {
if (stk.empty())
return -1;
return stk.begin()->second;
}
int max() {
if (aux.empty())
return -1;
return aux.begin()->first;
}
int pop() {
if (stk.empty())
return -1;
int id = stk.begin()->first, ret = stk.begin()->second;
stk.erase(stk.begin());
aux.erase({ret, id});
return ret;
}
int popmax() {
if (aux.empty())
return -1;
int ret = aux.begin()->first, id = aux.begin()->second;
aux.erase(aux.begin());
stk.erase({id, ret});
return ret;
}
};
int main(){
MaxStk max_stk;
max_stk.push(5);
max_stk.push(15);
max_stk.push(10);
cout << max_stk.top() << endl;
cout << max_stk.max() << endl;
cout << max_stk.popmax() << endl;
cout << max_stk.max() << endl;
cout << max_stk.pop() << endl;
cout << max_stk.top() << endl;
}
입력
max_stk.push(5)
max_stk.push(15)
max_stk.push(10)
max_stk.top()
max_stk.max()
max_stk.popmax()
max_stk.max()
max_stk.pop()
max_stk.top()
출력
10
15
15
10
10
5
마무리
두 개의 정렬된 set을 활용하면 push, pop, top, max, popmax 연산을 모두 O(log n) 시간 복잡도로 처리할 수 있습니다. 특히 popmax처럼 스택 중간에 있는 최댓값을 제거해야 하는 경우에도 set의 삭제 연산이 효율적으로 동작하기 때문에, 최대 스택 구현에 매우 적합한 방식입니다.