문제 개요
스택에 저장된 요소 중 최댓값을 O(1) 시간 안에 조회할 수 있는 스택을 구현한다고 가정해 보겠습니다. 여기서 중요한 제약 조건은 별도의 보조 스택과 같은 추가 공간을 사용하지 않아야 한다는 점입니다. 즉, O(1)의 보조 공간만 허용됩니다.
접근 방법
사용자 정의 스택 클래스를 만들어 현재 최댓값(stack_max)을 멤버 변수로 함께 관리합니다. 각 연산은 다음 규칙에 따라 동작합니다.
- peek 연산: 스택의 top 값이 현재 최댓값보다 크다면 실제 top 요소는 최댓값이므로 최댓값을 반환하고, 그렇지 않으면 top 값을 그대로 반환합니다.
- pop 연산: top 값이 최댓값보다 크면 실제 제거되는 요소는 최댓값입니다. 따라서 최댓값을 출력한 뒤, 이전 최댓값을
2 * stack_max - top공식으로 복원합니다. 그렇지 않으면 top 값을 그대로 출력합니다. - push 연산: 새로 삽입할 값 x가 현재 최댓값보다 크면, 원래 값 대신
2 * x - stack_max를 스택에 저장하고 최댓값을 x로 갱신합니다. 그렇지 않으면 x를 그대로 저장합니다.
이 트릭의 핵심은, 최댓값이 갱신될 때 저장하는 변형된 값 2 * x - stack_max가 항상 새로운 최댓값보다 크다는 점입니다. 이 덕분에 pop이나 peek 시점에 해당 위치의 실제 값이 무엇이었는지, 그리고 갱신되기 이전의 최댓값이 무엇이었는지 간단한 산술 연산만으로 역산할 수 있습니다.
C++ 구현 예제
#include <iostream>
#include <stack>
using namespace std;
class CustomStack {
stack<int> stk;
int stack_max;
public:
void getMax() {
if (stk.empty())
cout << "Stack is empty"<<endl;
else
cout << "Maximum Element in the stack is: "<< stack_max <<endl;
}
void peek() {
if (stk.empty()) {
cout << "Stack is empty ";
return;
}
int top = stk.top(); // 최상단 요소
cout << "Top Most Element is: "<<endl;
(top > stack_max) ? cout << stack_max : cout << top;
}
void pop() {
if (stk.empty()) {
cout << "Stack is empty"<<endl;
return;
}
cout << "Top Most Element Removed: ";
int top = stk.top();
stk.pop();
if (top > stack_max) {
cout << stack_max <<endl;
stack_max = 2 * stack_max - top;
} else
cout << top <<endl;
}
void push(int element) {
if (stk.empty()) {
stack_max = element;
stk.push(element);
cout << "Element Inserted: " << element <<endl;
return;
}
if (element > stack_max) {
stk.push(2 * element - stack_max);
stack_max = element;
} else
stk.push(element);
cout << "Element Inserted: " << element <<endl;
}
};
int main() {
CustomStack stk;
stk.push(4);
stk.push(6);
stk.getMax();
stk.push(8);
stk.push(20);
stk.getMax();
stk.pop();
stk.getMax();
stk.pop();
stk.peek();
}실행 결과
Element Inserted: 4 Element Inserted: 6 Maximum Element in the stack is: 6 Element Inserted: 8 Element Inserted: 20 Maximum Element in the stack is: 20 Top Most Element Removed: 20 Maximum Element in the stack is: 8 Top Most Element Removed: 8 Top Most Element is: 6
예제 동작 과정 살펴보기
위 예제에서는 4, 6, 8, 20 순서로 요소를 삽입합니다. 6이 삽입될 때 최댓값이 6으로 갱신되어 getMax()가 6을 출력하고, 이후 20이 삽입되면 최댓값이 20으로 갱신됩니다. 첫 번째 pop()이 실행되면 20이 제거되면서, 미리 저장해 둔 변형된 값으로부터 이전 최댓값 8이 복원됩니다. 두 번째 pop() 후에는 최댓값이 6으로 복원되며, 마지막 peek() 호출 시 남아 있는 최상단 요소인 6이 출력됩니다.
복잡도 분석
- 시간 복잡도: push, pop, peek, getMax 모든 연산이 O(1)에 수행됩니다.
- 공간 복잡도: 별도의 보조 스택 없이 멤버 변수 하나만 추가로 사용하므로 O(1)의 보조 공간이면 충분합니다.