개요
스택 안에서 최댓값(maximum element)을 저장하고, 이를 O(1) 시간에 조회할 수 있는 스택을 만들어야 한다고 가정해 봅시다. 여기서 중요한 제약 조건은 추가 공간을 O(1)만 사용해야 한다는 점입니다.
이 문제는 별도의 보조 스택 없이, 하나의 사용자 정의 스택으로 해결할 수 있습니다. 핵심 아이디어는 현재까지의 최댓값(stack_max) 변수 하나를 유지하면서, 새로 삽입되는 값이 기존 최댓값보다 클 경우 수학적 변환을 통해 이전 최댓값 정보를 인코딩하는 것입니다.
동작 원리
- peek(조회) 연산: 스택의 top 요소가 저장된 max보다 크다면 실제 top은 변환된 값이므로 max를 반환하고, 그렇지 않으면 top 요소를 그대로 반환합니다.
- pop(제거) 연산: top 요소가 max보다 크면 실제 제거되는 값은 max이며, 이전 최댓값은
2 * max - top_element공식으로 복원합니다. 그렇지 않으면 top 요소를 그대로 반환합니다. - push(삽입) 연산: 삽입할 값 x가 현재 max보다 크면 스택에는
2 * x - max값을 넣고, max를 x로 갱신합니다. 그렇지 않으면 x를 그대로 삽입합니다.
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(); // Top element.
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을 삽입하면 현재 최댓값은 6입니다.
- 8과 20을 추가로 삽입하면 최댓값은 20으로 갱신됩니다.
- pop을 실행하면 20이 제거되고, 최댓값은 자동으로 이전 값인 8로 복원됩니다.
- 다시 pop을 하면 8이 제거되고, peek 결과 최상단 요소는 6임을 확인할 수 있습니다.
이 방식은 보조 스택이나 배열 같은 추가 자료구조를 전혀 사용하지 않으면서도 모든 연산(push, pop, peek, getMax)을 O(1) 시간에 처리할 수 있다는 점에서 매우 효율적입니다.