💬 문제
MinStack 클래스 구현
MinStack() 생성자 함수
void push(int val) 스택에 val 삽입
void pop() 스택 가장 위의 요소 제거
int top() 스택 가장 위의 요소 반환
int getMin() 스택 내 요소 중 가장 작은 값 반환
모든 함수는 시간 복잡도가 O(1)이어야 함
✍️ 나의 풀이
var MinStack = function() {
this.stack = [];
this.min = [];
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
this.stack.push(val);
if (this.min.length === 0 || val <= this.min[this.min.length - 1])
this.min.push(val);
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
const num = this.stack.pop();
if (this.min[this.min.length - 1] === num)
this.min.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.min[this.min.length - 1];
};생성자 함수에서는 평범하게 스택처럼 저장할 배열 stack과
가장 적은 값을 구하기 위해 저장할 배열 min을 객체 속성으로 정의
push에서는 stack에 먼저 추가 후에
min이 비어서 최소값이 없는 상태거나
마지막 요소 값보다 새로 들어온 수가 같거나 작을 때 min에도 추가
그렇게 점점 더 작은 값만 min에 쌓여감
즉, 어느 시점에서든 min의 가장 마지막 요소가 최소값
pop에서는 stack에서 먼저 삭제
min에서는 가장 마지막 요소 값이 stack에서 pop된 값과 같다면 삭제
top은 stack 가장 마지막 요소 반환
getMin은 min 가장 마지막 요소 반환
📌 결과
Accepted
Runtime 91ms (Beats 50.79%)
Memory 59.65MB (Beats 25.24%)
📚 러닝 포인트
getMin을 O(1)으로 구현해야 한다는 점 때문에 정말 한참을 고민했다. 단순히 현재 최소값만 알고 넘어가면 안되고, pop 시에 다음 최소값을 찾을 수 있어야 하니 순서가 필요했다. 결국은 종이 한 장을 빼곡하게 채우면서 머리를 굴렸더니 감을 잡을 수 있었다. 모든 요소의 순위를 생각하지 않고 '현재의 최소값보다 더 작은 값'만을 챙기면 되었다. 그러다보면 각 구간에서의 최소값을 기록해둘 수 있고, stack의 특성 상 역순으로만 삭제가 가능하기 때문에 현재 최소값이 삭제되더라도 그 아래 영역의 최소값을 알 수 있다.
좀 더 쉬운 이해를 위해 그림을 그려봤다. 왼쪽은 배열로 표현한 것이고 오른쪽은 가상의 스택이라고 생각하자. 시간의 흐름으로 갱신된 최소값의 히스토리는 -2, -3, -5다. 따라서 -5, -3, -2 각각의 요소가 삭제되기 전까지, 즉 색상으로 구분한 영역이 존재하는 동안은 해당 값이 최소값이 되는 것이다.
