https://leetcode.com/problems/min-stack/?envType=study-plan-v2&envId=top-interview-150

155. Min Stack

⭐ 문제

스택을 디자인하세요. 그리고 push, pop, top, 그리고 최소 요소를 상수 시간내 검색을 지원해야 합니다.

• MinStack() : 스택 객채를 초기화
• void push(int val) : val을 스택에 push
• void pop() : 맨위 요소를 제거
• int top() : 맨 위 요소를 가져옴
• int getMin() : 스택의 최소 요소를 검색

0(1)의 시간복잡도로 해결책을 구현해야 합니다

🤔 고려해야할 사항

getMin을 쓸때 일반적으로 스택의 최소값을 구하기 위해 메서드 내에서 스택을 전부 조회해 버리면 시간 복잡도가 0(n)이 되어버려서 문제의 요구사항을 만족하지 못함. 따라서 getMin을 0(1)의 시간 복잡도로 구현하려면 스택을 조회하지 않고 min값이 바로 도출되어야함. 이를 위해선 getMin메서드 외에서 min값을 계산해주면 될거같음. 즉, 메서드마다 min값을 갱신하게 하면 될거 같음!

✍️ 의사 코드

1. 스택배열, min값을 초기화
2. push메서드는 스택에 값을 추가, min값 여부 확인
3. pop메서드는 스택이 비어있지 않다면 min값 여부를 확인하고 최상위 값 제거
4. top메서드는 스택이 비어있지 않다면 스택의 최상위 값을 호출
5. getMin메서드는 스택이 비어있지 않다면 min값을 호출

✅ 나의 풀이

class MinStack {
    private Stack<Integer> stack;
    private int min;

    public MinStack() {
        stack = new Stack<>();
        min = Integer.MAX_VALUE;
    }

    public void push(int val) {
        if (val <= min) {
            stack.push(min);
            min = val;
        }
        stack.push(val);
    }

    public void pop() {
        if (!stack.isEmpty()) {
            if (stack.peek() == min) {
                stack.pop();
                min = stack.pop();
            } else {
                stack.pop();
            }
        }
    }

    public Integer top() {
        if (!stack.isEmpty()) {
            return stack.peek();
        }
        return null;
    }

    public Integer getMin() {
        if (!stack.isEmpty()) {
            return min;
        }
        return null;
    }
}

🖥️ 결과

Runtime 0ms

👨‍💻 느낀 점

문제를 처음 봤을땐 단순하게 스택을 구현하는 문제인 줄 알았는데 시간복잡도를 고려해보니 일반적인 케이스와 달라서 당황하였습니다. 하지만 시간복잡도의 의미를 코딩테스트를 학습하면서 연습해 왔으므로 의미를 어느정도 파악할 수 있게되어서 문제 해결의 실마리를 잡을 수 있었습니다. 점점 발전하는 느낌이 들어서 자신감이 북돋아졌습니다. 🤗