참고
문제해설
NOTE
•
스택의 주요함수를 구현해서 최소 요소 검색을 지원하는 스택을 설계한다.
문제 로직고민
NOTE
•
어떤 방식으로 Stack을 구현할것인가?
◦
자바에는 Stack 라이브러리가 있지만, Stack을 구현하는 문제에서 이걸 사용하는건 문제의 목적과 맞지 않는것같아 직접 구현한다.
◦
동적배열과 Linked LIst 2개의 방식으로 가능하지만, 동적배열의 경우 크기 재할당 부분에서 비효율적인 면이 있을거라 생각해 Linked List로 구현한다.
•
어떻게 최소값을 빠르게 찾는가?
◦
2개의 Linked List를 활용한다.
◦
1개의 Linked List는 데이터를 담는 Stack으로 사용하고, 나머지 1개는 최소값을 확인하는 용도로 사용한다.
◦
push 단계에서는 최소값 Stack의 마지막 값과 비교해서 값이 더 작거나 같다면 값을 넣어준다.
◦
pop 단계에서는 최소값 Stack의 마지막 값과 동일하다면 값을 제거한다.
작성코드
NOTE
class MinStack {
LinkedList<Integer> stack;
LinkedList<Integer> minStack;
public MinStack() {
stack = new LinkedList();
minStack = new LinkedList();
minStack.add(Integer.MAX_VALUE);
}
public void push(int val) {
if(val <= minStack.getLast()) minStack.add(val);
stack.add(val);
}
public void pop() {
int val = stack.pollLast();
if(val == minStack.getLast()) minStack.pollLast();
}
public int top() {
return stack.getLast();
}
public int getMin() {
return minStack.getLast();
}
}
Java
복사
정답코드
NOTE
class MinStack {
int min;
int top;
int[] stack;
int[] minarr;
public MinStack() {
min=Integer.MAX_VALUE; top=-1; stack= new int[100000];
minarr= new int[10000];
}
public void push(int val) {
stack[++top]= val;
if(top==0){
min= val;
minarr[top]= val;
}
else{
min= Math.min(minarr[top-1], val);
minarr[top]= min;
}
}
public void pop(){
if(top!=-1){
top--;
}
}
public int top() {
return stack[top];
}
public int getMin() {
if(top==-1){ return -1;}
return minarr[top];
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
2개의 Stack을 기본배열형식으로 진행했다.
•
제약조건에 명령어 길이가 30000인데 왜 배열의 길이를 10000으로 잡은지는 모르겠다.
•
로직을 보니 생각보다 훨씬 간단해서 단순 배열로 구현하는게 더 좋았던것 같기도하다. 30000이라는 크기가 성능에 큰 영향을 미치는 급도 아니라고 생각된다.