🔍 문제
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack()initializes the stack object.void push(int val)pushes the element val onto the stack.void pop()removes the element on the top of the stack.int top()gets the top element of the stack.int getMin()retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
문제 해석
스택이라는 자료구조를 구현하는 문제이다. 스택을 클래스로 정의하고, 요구사항에 맞는 함수들을 구현해야한다. 일반 스택을 구현하는 문제인 것 같지만, 스택의 가장 최솟값을 구하는 함수가 추가되어있다.
또한 클래스 내의 함수들의 시간 복잡도는 O(1)로 구현해야하는 조건이 있다.
문제 링크
📝 문제 풀이
1. 문제 풀이에 필요한 개념 공부하기
스택(Stack)
스택은 나중에 들어온 요소가 가장 먼저 나가게 되는 LIFO(Last In First out) 형태의 자료구조다.push연산을 수행하면 스택 맨 위에 데이터가 들어온다.pop연산을 수행하면 스택의 가장 맨 위에 위치한 데이터를 가져온다.
2. 문제 접근을 위한 생각
최솟값을 어떻게 구할까?
일반 스택 문제라면, 데이터를 맨 위에 넣고 가져올 때는 맨 위 데이터를 가져오는 방식으로 구현하면 된다. 그러나 이번 문제에서는 스택에서의 최솟값이 무엇인지도 알 수 있어야한다. 또한 모든 함수는 시간 복잡도가 상수 시간이어야 하므로, 정렬과 같은 방식으로 최솟값을 구할 수는 없다.
스택 자료구조 뿐만 아니라 최솟값을 저장할 자료구조가 필요하다. 상수 시간에 찾기 위해 최솟값을 저장할
min을 정의했다
스택 자료구조는 어떻게 정의할까?
자바스크립트의 배열은 push(), pop() 메소드가 존재한다. push()는 배열 맨 뒤에 데이터를 넣어주고, pop()은 배열 맨 뒤에 데이터를 가져오는 역할을 한다. 따라서 자바스크립트에서의 스택은 배열로 간단하게 사용할 수 있다.
3. 문제 해결방법
스택에 데이터를 저장하고, 데이터를 가져오는 경우는 push(), pop() 함수를 이용했다. top()의 경우도 스택에 가장 맨 위 데이터를 가져오는 것이므로 스택 배열의 맨 마지막 요소를 반환하도록 정의했다.
최솟값을 어떻게 저장해야하는지 예시를 통해 알아보자.
push()는 -2, 0, -3 순서대로 수행한다. 그렇다면 스택에는 [-2, 0, -3]이 저장되어야하는데 이때 최솟값은 어떻게 저장해야할까?
- 초기 최솟값을
2**31로 설정했다. 스택에는2**31-1이하의 수만 들어오기 때문에2**31을 가장 큰 값으로 설정해도 문제가 없기 때문이다. - 스택에 -2를 넣어라는 push(-2) 명령어를 실행해야한다.
- -2는 2**31보다 작으므로, 최솟값 min을 저장하는 곳에 -2로 바꾸어주고 스택에는 -2를 넣어주면 된다.
- 그런데 위 방법은 문제가 있다.
만약 pop() 명령을 통해 -2를 제거하게 되면 스택에서의 최솟값은 여전히 -2일까? 아니다. 이런 경우를 대비해 다음 최솟값도 알아야하는데, 그러면 최솟값을 다시 배열로 정의해서 저장해야할까? 그렇다면 시간 복잡도 O(1) 조건을 만족하기 어렵다.
그렇다면 상수 시간에 최솟값을 구하기 위해 다음 최솟값을 어떻게 기억할까?
- push()를 실행해서 들어오는 값이 현재 최솟값보다 작은 값이라면, 현재 최솟값을 먼저 스택에 넣어주고 push할 값을 넣어준다.
- 위 말이 쉽게 이해가 안된다. 그럼 저 상태에서 pop()을 수행해보자.
pop()을 한 번 실행하면 맨 위 -2가 나오게 된다. 그런데 최솟값
min = -2가 나오게된다. 그렇다면 pop()에서는 최솟값 min이 나오게 될 경우에 한 번 더 pop()을 실행해 min을 업데이트 시켜준다.- push()를 실행해서 최솟값이 갱신될 때, 기존의 최솟값을 넣어준다. 기존의 최솟값은 2번째로 작은 값이므로, 만약 최솟값이 pop()되면 2번째로 작은 최솟값도 함께 pop()해서 자신이 최솟값으로 업데이트 되는 것이다.
데이터를 더 넣은 후 이해해보자.
- 스택에 0을 넣을 때는 0은 최솟값보다 큰 값이므로 0만 스택에 넣으면 된다.
- 스택에 -3을 넣는 경우는 중요하다. 최솟값 -2보다 넣고자하는 값 -3이 더 작기 때문이다. 그렇다면 동작은 다음과 같이 일어난다.
현재 최솟값 -2를 스택에 넣는다. 그리고 넣을 -3은 현재 최솟값보다 작으므로 -3을 최솟값으로 업데이트시켜주고, -3을 스택에 넣어준다.
위 상태에서 pop()을 수행하는 걸 한 번 더 생각해보자.
그럼 현재 최솟값 -3을 빼야하는데, -3을 스택에서 제거하게 되면 스택의 최솟값은 -3이 아니다. 그러나 -3을 넣을 때 2번째로 작은 값이 된 -2를 같이 스택에 넣었기 때문에, 이를 pop() 해준 후 최솟값으로 업데이트 시켜주면 된다.
📝 실수 돌아보기
처음에 최솟값을 배열이 아닌 그냥 상수로 저장하는거까진 생각했다. 그러나 최솟값이 pop() 되는 경우를 고려하지 못했고, 최솟값이 스택에서 사라지고 나서도 계속 최솟값을 출력할 때 처음 설정한 최솟값으로 수행되게 했다.
💡 학습 정리
JSDoc 주석
/**
@param {string} param1
@param {number} param2
@return {number}
*/
function example(param1, param2) {
...
}코드에 함수마다 주석이 있었다. JSDoc 주석으로 매개변수와 반환 값에 대한 정보를 제공하는 역할을 한다. 코드 문서화를 위해 사용하는데, IDE나 문서 생성 도구에서 코드 문서를 자동으로 생성할 때 활용된다.
IDE에서 함수에 마우스 오버하면 해당 함수의 파라미터와 리턴 값으로 어떤 자료형이 들어오는지 볼 수 있다. 타입스크립트와 달리 런타임 시 타입이 결정되는 동적 타입 언어는 자바스크립트에서 타입 에러가 많이 발생하는데, 해당 기능을 통해 점검할 수 있다는 것을 배웠다.
⌨️ 작성한 코드
var MinStack = function() {
this.stack = [];
this.min = 2**31;
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
if (this.min >= val) {
this.stack.push(this.min);
this.min = val;
}
this.stack.push(val);
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
if (this.stack.length > 0) {
const popNubmer = this.stack.pop();
if (popNubmer === this.min) {
this.min = this.stack.pop();
}
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length-1];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.min;
};