LeetCode 155 Min Stack

nayu1105·2023년 8월 29일

leetcode 알고리즘

LeetCode

목록 보기

16/28

LeetCode 155 Min Stack 풀러가기

문제

MinStack class를 구현하면 된다.

Minstack 기본 생성자 : stack 객체를 초기화한다.
void push(int val) : val 을 stack에 추가한다.
void pop() : stack에서 top 요소를 제거한다.
int top() : stack에서 top 요소를 리턴한다.
int getMin() : 현재 스택에서 가장 최소값을 반환한다.

문제 분석

첫번째 시도

첫번째는 쉽게 짤 수 있는 방법을 고려했다.

java.util 클래스에 있는 Stack과 활용하여 stack을 따로 구현할 것도 없고,
stack의 push, pop에 의해 계속 변하는 최솟값도 PriorityQueue를 활용하여 쉽고 빠르게 찾으려고 했다.

MinStack 기본 생성자 : private final로 stack과 queue를 선언하고, 생성자 함수에서 이를 초기화하였다.
void push(int val) : stack에 val을 push하고, queue에도 val을 add한다.
void pop() : stack.peek를 활용해 top요소를 가져오고, 이를 queue.remove를 활용하여 제거한다. 그리고 stack.pop을 활용해서 top 요소를 제거했다.
int top() : stack.peek를 활용했다.
int getMin() : queue.peek를 활용해 우선순위가 가장 높은(오름차순) 요소를 반환했다.

코드

import java.util.*;

class MinStack {

    private final Stack<Integer> stack;  

    private final PriorityQueue<Integer> queue;

    public MinStack() {
        stack = new Stack<>();
        queue = new PriorityQueue<>();
    }
    
    public void push(int val) {
        stack.push(val);
        queue.add(val);
    }
    
    public void pop() {
        int val = stack.peek();
        stack.pop();
        queue.remove(val);
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return queue.peek();
    }
}

/**
 * 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();
 */

결과 : 성공

Runtime

Memory

Stack, PriorityQueue 라이브러리를 사용해서 메모리를 걱정했는데 괜찮았다.

그러나 시간이 오래 걸렸다.

원인은 qeuue.remove할 때 시간복잡도가 N(logn)이기 때문인 것 같다.

만약 stack의 최솟값을 바로 알아서 삭제할 수 있다면 N(1)을 만들 수 있을 것 같았다

두번째 시도

위의 코드에서 Stack<Integer>을 사용하고, PriorityQueue<Integer>을 사용하여 최솟값을 구했다.

최솟값 연산을 빠르게 하기 위해 Stack을 Integer로 저장하지 않고,

Node라는 클래스를 만들고, Node에 현재 노드까지에서의 최솟값을 인자로 가지도록 하였다.

코드

import java.util.*;

class MinStack {

    private Stack<Node> stack;  

    public MinStack() {
        stack = new Stack<>();
    }
    
    public void push(int val) {
        if(stack.size() == 0){stack.push(new Node(val, val));}
        else{
            stack.push(new Node(val, val < stack.peek().min ? val : stack.peek().min));
        }        
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek().val;
    }
    
    public int getMin() {
        return stack.peek().min;
    }

    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();
 */

결과 : 성공

Runtime

Memory

다른분의 풀이

시간을 더 줄이는 방법이 무엇일까 고민하다가 다른분의 풀이와 비교해보았다.

다른 분은 더미 head를 미리 두어서 push 때 stack사이즈를 비교하는 연산을 줄였다.

큰 차이점은 직접 Stack을 구현한 것이였다. 이분의 코드를 보고 다시 한 번 고쳐보았다.

Rumtime : 3ms

코드

class MinStack {

    int min;
    Node head;
    Node dummy;

    class Node {
        int val;
        Node next;
        int prevMin;
        Node(int val, Node next, int prevMin) {
            this.val = val;
            this.next = next;
            this.prevMin = prevMin;
        }
    }

    public MinStack() {
        dummy = new Node(Integer.MAX_VALUE,null,Integer.MAX_VALUE);
        head = dummy;
        min = dummy.val;
    }
    
    public void push(int val) {
        Node node = new Node(val, head, min);
        if (val < min) {
            min = val;
        }
        head = node;
    }
    
    public void pop() {
        if (head.val == min) {
            min = head.prevMin;
        }
        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return 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();
 */

세번째 시도

코드

class MinStack {

    Node head;

    public MinStack() {
       head = new Node(Integer.MAX_VALUE, Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        head = new Node(val, head.min < val ? head.min : val, head);
    }
    
    public void pop() {
        head = head.pre;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return head.min;
    }

    class Node{
        int val;
        int min;
        Node pre;

        public Node(int val, int min){
            this.val = val;
            this.min = min;
        }

        public Node(int val, int min, Node pre){
            this.val = val;
            this.min = min;
            this.pre = pre;
        }
    }
}

/**
 * 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();
 */