[Grind75-LeetCode] Min Stack JAVA

알고리즘/코딩테스트-Grind75

[Grind75-LeetCode] Min Stack JAVA

kwang2134 2024. 10. 29. 14:52

728x90

[Grind75-LeetCode] Min Stack - Medium

접근

스택 + 우선순위 큐
스택 + 스택
스택 + 객체
객체 (연결 리스트)

풀이

기본적인 스택에 최솟값을 반환받을 수 있는 최소 스택을 구현하는 문제이다. 간단하게 생각하여 풀 수 있는 두 가지 방법을 먼저 풀어보고 가장 좋은 성능을 보여준 코드를 가져왔다.

스택 + 우선순위 큐

가장 쉽게 풀 수 있으나 성능이 좋지 않은 방법이다. 내부에 기본 스택 연산을 위한 스택 하나와 최솟값 반환을 위한 우선순위 큐를 두고 푸는 방식이다.

class MinStack {
    private Stack<Integer> stk;
    private PriorityQueue<Integer> pq;

    public MinStack() {
        stk = new Stack<>();
        pq = new PriorityQueue<>();
    }

    public void push(int val) {
        stk.push(val);
        pq.offer(val);
    }

    public void pop() {
        pq.remove(stk.pop());

    }

    public int top() {
        return stk.peek();
    }

    public int getMin() {
        return pq.peek();
    }
}

포인트는 스택과 우선순위 큐를 동기화시키기 위해 pop() 연산 발생 시 해당하는 요소를 우선순위 큐에서도 제거하는 것인데 remove 메서들 통해 제거했다. 큐의 경우 일반적으로 선입선출 구조로 먼저 들어간 것이 먼저 나오는 구조로 먼저 들어간 순서대로 꺼내게 되는 것이 정석이다. 그러나 어쨌든 우선순위 큐는 큐를 상속받고 큐는 자바의 컬렉션을 상속받기 때문에 컬렉션의 특정 요소를 제거할 수 있는 remove 메서드가 사용가능 한 것이다. remove 메서드는 내부 루프를 돈 다음에 매칭되는 요소를 찾게 되면 밖으로 꺼내게 된다. 그렇기에 기본적인 remove 연산은 O(n)의 시간 복잡도를 가진다. 일반적으로 스택과 기본 큐의 pop(), poll() 연산은 O(n)의 시간 복잡도로 수행이 되고 우선순위 큐의 poll()은 O(logn)으로 remove 연산 하나에서 수많은 시간을 잡아먹게 되어 성능상으론 좋지 않은 코드이다.

스택 + 스택

우선순위 큐 대신 스택을 두 개 사용하는 방식이다. 기본 적인 연산을 위한 스택과 최솟값을 위한 보조 스택으로 구성된다. 해당 코드는 5ms 실행 시간으로 풀어졌던 샘플 코드에서 가져왔다.

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.isEmpty() || minStack.peek()>=val){
            minStack.push(val);
        }
    }
    
    public void pop() {
        int popped = stack.pop();
        if(popped == minStack.peek()){
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }

}

기본 스택과 최솟값을 위한 스택을 사용한다. 작동 원리를 설명하면 기본 스택은 입력받는 연산을 그대로 수행한다. 연산을 수행하며 최솟값 스택에는 두 가지 경우에만 값이 들어가게 된다. 최솟값 스택이 아무것도 들어있지 않아 비어있는 경우, 최솟값 스택에 상단이 현재 값 보다 큰 경우 이렇게 두 경우에 push가 일어나게 되고 그냥 한마디로 push가 들어올 때 현재 최솟값 보다 작다면 스택에 추가시켜 최솟값으로 정렬된 스택을 만드는 것이다. 그렇게 되면 pop 연산 수행 시 최솟값 스택의 상단과 값이 동일하다면 현재 스택에 들어있던 최솟값이 꺼내진 걸로 최솟값 스택에서도 해당 값을 뽑아 그다음 최솟값으로 맞춰준다. 그렇게 되면 최솟값 스택 상단은 항상 스택 내 가장 작은 값이 되게 되고 peek()와 pop() 모두 O(1)의 시간 복잡도를 가지므로 좀 더 효율적인 코드가 된다.

스택 + 객체

스택에 정수값 대신 정수값과 최솟값을 가지는 객체를 넣어 구현한 방식이다. 객체를 통해 최솟값과 현재값에 접근하여 하나의 스택만 사용하여 구현되었다. 4ms 실행 시간을 가졌던 샘플 코드를 가져온 내용이다.

class MinStack {
    class Pair{
        int first;
        int second;
        Pair(int first, int second){
            this.first = first;
            this.second = second;
        }
    }

객체는 이너 클래스로 구현이 되어있다. 현재값인 first와 최솟값인 second를 가진다.

    Stack<Pair> stack;
    public MinStack() {
        stack = new Stack<>();
    }
    
    public void push(int val) {
        if(stack.isEmpty()){
            stack.push(new Pair(val, val));
        }else{
            stack.push(new Pair(val, Math.min(val, stack.peek().second)));
        }
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek().first;
    }
    
    public int getMin() {
        return stack.peek().second;
    }
}

스택을 생성하고 스택이 비어있는 경우 현재값으로 최솟값을 채운 뒤 삽입한다. 스택에 요소가 존재한다면 현재 스택 상단 객체의 최솟값과 현재 삽입할 값을 비교하여 더 작은 값으로 second를 설정한 뒤 삽입한다. 이렇게 되면 각 스택에 삽입되어 있는 객체가 스택에 삽입될 때까지의 최솟값을 가진 채로 들어가기 때문에 최솟값 관리를 자연스럽게 할 수 있다.

객체 (연결 리스트)

가장 좋은 성능을 자랑했던 코드로 Beats 100%를 만족하는 코드이다. 연결 리스트 방식의 객체를 통해 구현한 방법으로 객체에는 현재 값, 최솟값, 다음 객체의 참조가 들어있다.

class Node {
    int val;
    int msf;
    Node next;

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

구현에 사용되는 객체이다. 현재값, 최솟값, 다음 노드의 참조를 가지고 있다.

class MinStack {

    Node head = null;

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

구현된 코드이다. 비어있는 노드를 생성하고 push 연산이 수행되면 노드를 연결한다. 이 코드에서 굉장히 헷갈리는 부분이 하나 있다. 바로 다음 노드를 연결하는 포인터인 next인데 이게 다음 노드를 가리킨다는 의미에서 정의된 이름이지만 현재 구조를 어떻게 받아들이냐에 따라 헷갈릴 수 있다. 일반적인 연결 리스트를 구현할 때 노드 1 -> 노드 2 -> 노드 3과 같이 이전 노드가 새로 생성된 노드를 가리키는 방식으로 구현된다. 그렇기 때문에 현재 코드와 같이 노드 1 <- 노드 2 <- 노드 3과 같은 형태로 연결된다면 next가 아니라 previous로 이전 노드라는 이름이 더 알맞지 않나 생각할 수 있다. 그러나 이 코드는 연결 리스트로 스택을 구현한 것이기 때문에 포인터가 제일 최근에 생성된(스택 상단)을 가리키고 pop() 연산 수행 시 이전 노드가 상단이 되어야 하기 때문에 next라는 이름이 맞는 표현이다.

연결 구조 null <- 노드1 <- 노드2 <- 노드3(head)
head가 제일 최근 생성된 노드를 가리킴 -> 스택에 제일 최근 추가된 요소를 가리킴(스택 상단)

push()연산 발생 시
노드4가 생성되며 노드4의 다음(next) 포인터로 노드3이 연결되고 head 포인터가 노드4로 이동
null <- 노드1 <- 노드2 <- 노드3 <- 노드4(head)

pop() 연산 발생 시
노드4(head)의 포인터를 노드3로 옮김 -> pop() 연산 수행 시 노드4에서 다음(next)으로 이동될 포인터를 나타냄
null < 노드1 <- 노드2 <- 노드3(head)

push 연산으로 노드 생성 시 현재 최솟값과 새로운 최솟값을 각 노드에 저장하기 때문에 최솟값을 쉽게 반환할 수 있다.

전체 코드

스택 + 우선순위 큐

class MinStack {
    private Stack<Integer> stk;
    private PriorityQueue<Integer> pq;

    public MinStack() {
        stk = new Stack<>();
        pq = new PriorityQueue<>();
    }

    public void push(int val) {
        stk.push(val);
        pq.offer(val);
    }

    public void pop() {
        pq.remove(stk.pop());

    }

    public int top() {
        return stk.peek();
    }

    public int getMin() {
        return pq.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();
 */

스택 + 스택

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.isEmpty() || minStack.peek()>=val){
            minStack.push(val);
        }
    }
    
    public void pop() {
        int popped = stack.pop();
        if(popped == minStack.peek()){
            minStack.pop();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.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();
 */

스택 + 객체

class MinStack {
    class Pair{
        int first;
        int second;
        Pair(int first, int second){
            this.first = first;
            this.second = second;
        }
    }
    Stack<Pair> stack;
    public MinStack() {
        stack = new Stack<>();
    }
    
    public void push(int val) {
        if(stack.isEmpty()){
            stack.push(new Pair(val, val));
        }else{
            stack.push(new Pair(val, Math.min(val, stack.peek().second)));
        }
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek().first;
    }
    
    public int getMin() {
        return stack.peek().second;
    }
}

/**
 * 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 Node {
    int val;
    int msf;
    Node next;

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

    Node head = null;

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

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

728x90

'알고리즘 > 코딩테스트-Grind75' 카테고리의 다른 글

[Grind75-LeetCode] Number of Islands JAVA (1)	2024.10.31
[Grind75-LeetCode] Validate Binary Search Tree JAVA (0)	2024.10.30
[Grind75-LeetCode] Product of Array Except Self JAVA (0)	2024.10.28
[Grind75-LeetCode] Coin Change JAVA (0)	2024.10.27
[Grind75-LeetCode] Implement Trie (Prefix Tree) JAVA (0)	2024.10.26

현재글[Grind75-LeetCode] Min Stack JAVA

kwang2134 님의 블로그

개발/ 알고리즘/깃허브 https://github.com/kwang2134

leetcode, spring data JPA, 프로그래머스, BFS, 코딩테스트, 스프링, 알고리즘, 오블완, programmers, spring, 티스토리챌린지, Java, grind75, 백준, dfs, blind75, neetcode, 자바, 웹 개발, DP,

Today :
Yesterday :

kwang2134 님의 블로그