https://leetcode.com/problems/min-stack
평가
결과 : 3회 실패 후 성공
풀이시간 : 전체 1시간 10분
첫 시도
첫 시도에서 우선순위 큐를 사용해 문제를 풀려고 시도했습니다.
N * 로그 시간복잡도를 갖지만 우선은 돌아가는 코드를 만들고 리팩토링하려했습니다.
하지만 아래 경우를 생각하지 못했고, 틀렸습니다.
스택에 -2 -> 0 -> -1 -> -5 순서로 저장되었을 때, 가장 작은 값 -5가 없어지면 최소값은 -2입니다.
그 다음 스택에서 값을 빼면(-1빠짐) 최소값은 -2로 그대로인데, 이걸 고려하지 않고 우선순위 큐에서 가장 최상단 값인 -2를 빼버렸습니다.
즉, 스택에서 2개를 빼면 가장 최소값은 -2인데, -1이 나오는 결과를 가져왔습니다.
두 번째 시도
어떻게 스택에서 최소값을 찾을 때 O(1)의 시간복잡도로 갖게 할 수 있을까?
해당 문제에 대해 고민을 많이 했습니다.
생각했던 아이디어는 아래와 같습니다.
스택 내부에는 배열, PriorityQueue, 임시저장소를 갖습니다.
add가 일어나면 배열과 PriorityQueue에 값을 추가합니다.
pop이 일어날 때는 다음과 같은 동작이 일어납니다.
1. `삭제되는 값`과 `현재 스택의 최소값`과 비교합니다.
2-1. 만약 현재 스택의 최소값보다 큰 값이 삭제되면, 임시저장소에 저장합니다.
2-2. 만약 삭제되는 값이 현재 스택의 최소값과 일치한다면,
PriorityQueue에서 해당 값과 임시저장소에 있는 모든 값을 삭제합니다.해당 방식으로 코드를 작성하면 작동에는 문제가 없을 거 같은데 시간복잡도를 만족할 수 없습니다.
우선순위 큐를 써서는 시간복잡도를 해결할 수 없다는 판단을 하고 아예 풀이를 바꿉니다.
정답 아이디어 (세 번째 시도)
해당 문제의 시간복잡도는 O(1) 입니다. 그러면 사실 방법은 하나라는 생각이 들었습니다.
스택을 넣고 빼는 연산이 일어날 때 -> 그 순간에 최소값이 무엇인지 알아야 한다.
그러다가 스택에 지금까지의 최소값을 저장하면 되는 게 아닐까 하는 아이디어를 얻었습니다.
스택은 누적이 됩니다. 나를 기준으로 나보다 먼저 들어온 값들은 나보다 빨리 나갈 수 없습니다.
그래서 최소값은 누적으로 계산할 수 있습니다.
아이디어는 다음과 같습니다.
1. push 연산 시, 스택에 Node를 저장합니다.
- Node는 현재 값과 스택의 최소값을 저장합니다.
2. pop 연산 시, 삭제되는 Node를 확인합니다.
- 만약 삭제되는 Node의 value가 스택의 최소값과 일치한다면, 최소값의 갱신이 일어납니다
- 스택의 최소값은 스택의 가장 top에 위치하는 Node에서 확인할 수 있습니다.정답 코드
class MinStack {
List<Node> store;
int topIdx; // push시 들어가야 할 인덱스
Integer min;
public MinStack() {
this.store = new LinkedList<>();
this.topIdx = 0;
}
public void push(int val) {
if (topIdx == 0) {
min = val;
} else {
min = Math.min(val, min);
}
store.add(new Node(val, min));
topIdx++;
}
public void pop() {
if (isEmpty()) {
throw new RuntimeException();
}
Node removed = store.remove(--topIdx);
if (removed.val == min) {
Node top = topHelper();
if (top == null) {
this.min = null;
} else {
this.min = top.min;
}
}
}
private Node topHelper() {
if (topIdx == 0) {
return null;
}
return store.get(topIdx - 1);
}
public int top() {
return topHelper().val;
}
public int getMin() {
if (isEmpty()) {
throw new RuntimeException();
}
return min;
}
private boolean isEmpty() {
return store.size() == 0;
}
static class Node {
int val;
int min;
public Node(int val, int min) {
this.val = val;
this.min = min;
}
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/