125. Min Stack

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

문제

아래를 지원하는 stack을 설계하자.

각 함수는 O(1)의 시간 복잡도를 가져야 한다.

• MinStack(): 스택 객체를 초기화
• void push(int val): 요소 val을 스택에 추가
• void pop(): 스택의 맨 위에 있는 요소 제거
• int top(): 스택의 최상위 요소 반환
• int getMin(): 스택의 최소 요소 검색

나의 풀이

접근

여기서 가장 중요한 포인트는 getMin, 스택의 최소 요소 검색을 O(1)의 시간 복잡도로 수행해야 한다는 점이다.

스택의 최소 요소 검색을 구현하려면 어떻게 해야할까?

• push / pop 연산마다 최소값을 비교 ❌
  • MinStack의 변수로 관리를 한다면, pop을 할 때, 반드시 전체 요소를 순회해서 최소값을 정해야하기 때문에 O(n) 시간복잡도를 가진다.
• 스택의 각 노드마다 그때 당시의 최솟값을 기록 ✅
  • 스택의 각 노드의 push 연산마다, 값과 함께 그때의 최소값을 기록하는 방식 → 스택의 최상위 노드가 가지는 최솟값을 보면 지금까지 저장된 모든 요소의 최소값을 알 수 있다. 따라서 O(1) 시간복잡도를 가진다.

구현 코드

class MinStack {
    Node head;
    class Node {
        int min;
        int val;
        Node next;

        Node(int min, int val, Node next) {
            this.min = min;
            this.val = val;
            this.next = next;
        }
    }
    public MinStack() {
        head = null;
    }
    
    public void push(int val) {
        int min = (head==null) ? val : head.min;
        Node newNode = new Node(Math.min(min, val), val, head);
        head = newNode;
    }
    
    public void pop() {
        if (head.next == null || head == null) {
            head = null;
            return;
        }

        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return head.min;
    }
}

• MinStack()
  • head = null로 초기화
• void push(int val)
  • 이미 스택에 노드가 있다면, head의 min값과 push하려는 값을 비교해 min값을 넣는다.
  • 이미 스택에 노드가 없다면, 현재 값을 min값으로 넣는다.
  • newNode의 next를 head로 가리키게 한 다음, head를 newNode로 변경
• void pop()
  • 스택에 값이 하나만 있거나, 하나도 없는 상태라면, head를 null로 할당
  • 위 경우가 아니라면, head를 head의 next로 변경
• int top()
  • head의 값을 return
• int getMin()
  • head의 min 값을 return

결과

---

다른 풀이

class MinStack {
	private Node head;
        
    public void push(int x) {
        if (head == null) 
            head = new Node(x, x, null);
        else 
            head = new Node(x, Math.min(x, head.min), head);
    }
    
    public void pop() {
        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return head.min;
    }
        
    private class Node {
        int val;
        int min;
        Node next;
            
        private Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}

이 풀이가 leetcode에서 Java로 작성한 풀이 중 가장 극찬을 받고 있는 코드였다. 나와 비슷한 코드긴 하지만, 한 가지 더 간결하게 작성한 부분인 pop()이 다르다.

아래와 같은 조건을 놓쳤기 때문이다.

• Methods pop, top and getMin operations will always be called on **non-empty** stacks.

pop, top, getMin 함수는 스택이 비어있을 때 호출되지 않는다는 조건이다. top과 getMin은 봤는데, pop을 놓쳤었다.

코테에서는 조건도 정말 꼼꼼히 다 읽어봐야 한다. 하나의 조건 유무 또한 코드에 큰 영향을 미칠 수 있다.