[LeetCode Top Interview 150] [Stack] 155. Min Stack

[LeetCode Top Interview 150]

[문제 링크]

[Stack] 155. Min Stack

[문제 설명]

push, pop, top, minimum element 검색을 지원하는 stack을 설계하여라.

• MinStack() : stack 개체를 초기화
• void push(int val) : 요소를 val stack에 푸시
• void pop() : stack 맨 위에 있는 요소를 제거
• int top() : stack의 최상위 요소를 가져옴
• int getMin() : stack에서 최소 요소를 검색

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"][],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

[내가 생각해 본 방법]

직접 Stack을 정의하는 것도 방법이겠지만, 수업 시간에 배운 ArrayList를 활용하는 방법으로 문제를 풀어보면 좋을 것 같다는 생각을 했다. 2개의 ArrayList를 선언해서 풀면 효과적으로 풀어볼 수 있을 것 같았다.

[시행 착오 코드1]

class MinStack {

    ArrayList<Integer> stack;
    ArrayList<Integer> minStack;

    public MinStack() {
        stack = new ArrayList<>();
        minStack = new ArrayList<>();
    }

    public void push(int val) {

        stack.add(val);
        if(minStack.isEmpty()){
            minStack.add(val);
        }
    }

    public void pop() {
        stack.remove(stack.size());
        minStack.remove(stack.size());
    }

    public int top() {
        return stack.get(stack.size());

    }

    public int getMin() {
        return minStack.get(minStack.size());
    }
}

1) stack과 minStack을 선언하고
2) MinStack() : 생성자에서 각각 초기화해준다.
3) void push(int val) : stack에 매개변수 val 값을 추가하고, 만약에 minStack에 값이 없다면 minStack에도 값을 추가해준다.
4) void pop() : stack의 최상단(마지막) 값을 제거하고, minStack의 최상단(마지막) 값도 제거한다.
5) int top() : stack의 최상단(마지막) 값을 가져온다.
6) int getMin() : minStack의 최상단(마지막) 값을 가져온다.

처음 작성했던 코드인데, 최상단(마지막) top 값을 구하기 위해서는 인덱스가 0부터 시작하므로, size에서 -1을 해줘야 한다는 것을 간과하고 있었다. 그리고 pop() 메서드에서도 minStack의 top 값을 제거해줘야 하는데, stack의 값을 제거하고 있었다. 그리하여 다시 수정한 코드

[최종 제출 코드] : 추가 개선

추가적으로 해야할 부분들

• 시간 복잡도, 공간 복잡도 개선하기
• 다른 사람들이 풀이한 다양한 코드 확인 해보기

class MinStack {

    ArrayList<Integer> stack;
    ArrayList<Integer> minStack;

    public MinStack() {
        stack = new ArrayList<>();
        minStack = new ArrayList<>();
    }

    public void push(int val) {

        stack.add(val); //stack에 값 추가
        if(minStack.isEmpty()){ //minStack이 비어있다면,
            minStack.add(val);  //minStack에 val 요소 값 추가
        }else   //minStack에 이미 값이 있다면,
            minStack.add(Math.min(minStack.get(minStack.size()-1),val));  
            //Math 함수를 사용하여 이미 존재하는 minStack의 top의 값을 꺼내고, val 요소와 비교하여, 최소값을 minStack에 넣어줌
    }

    public void pop() {
        stack.remove(stack.size()-1);   //stack의 top 값 제거
        minStack.remove(minStack.size()-1); //minStack의 top 값 제거
    }

    public int top() {
        return stack.get(stack.size()-1); //stack의 top 값 가져옴
    }

    public int getMin() {
        return minStack.get(minStack.size()-1); //minStack의 top 값 가져옴
    }
}