리트코드 - 155. Min Stack

리트코드 - 155. Min Stack

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

 

문제 설명

push, pop, top 및 최소 요소를 상수 시간 내에 검색하는 기능을 지원하는 stack을 설계하세요.

MinStack 클래스를 구현하세요:
MinStack()는 스택 객체를 초기화합니다.
void push(int val)는 요소 val을 스택에 추가합니다.
void pop()는 스택의 맨 위 요소를 제거합니다.
int top()는 스택의 맨 위 요소를 가져옵니다.
int getMin()은 스택에서 최소 요소를 검색합니다.

각 함수에 대해 O(1) 시간 복잡도를 가진 솔루션을 구현해야 합니다.

 

의사코드

클래스 MinStack     정수 head     정수 minHead     정수 array     정수 배열 minArray     정수 배열 capacity     생성자         head = -1         minHead = -1         capacity = 3 * 10000         array = 길이 capacity 배열 생성         minArray = 길이 capacity 배열 생성         함수 push(정수 val)         if (head가 capacity -1와 같으면)             오버 플로 예외         if (head == -1 또는 minArray[minHead] >= val)             minArray[++minHead] = val                  array[++head] = val              함수 pop()         if (head == -1)             언더 플로 예외                 if (minArray[minHead] == array[head] 이면서 minHead != 0)             minHead--         head--          함수 top()         if (head < 0)             -1 리턴                 array[head] 리턴          함수 getMin()         if (minHead != -1)             minArray[minHead] 리턴                 Integer.MIN_VALUE 리턴     클래스 끝

 

풀이코드

class MinStack {
    private int head;
    private int minHead;
    private int[] array;
    private int[] minArray;
    private int capacity;

    public MinStack() {
        head = -1;
        minHead = -1;
        capacity = 3 * 10000;
        array = new int[capacity];
        minArray = new int[capacity];
    }
    
    public void push(int val) {
        if (head == capacity - 1) {
            throw new RuntimeException("Stack Overflow Exception!");
        }

        if (head == -1 || minArray[minHead] >= val) {
            minArray[++minHead] = val;
        }
 
        array[++head] = val;
    }
    
    public void pop() {
        if (head == -1) {
            throw new RuntimeException("Stack Underflow Exception!");
        }

        if (minArray[minHead] == array[head] && minHead != 0) {
            minHead--;
        }

        head--;
    }
    
    public int top() {
        if (head < 0) {
            return -1;
        }
        return array[head];
    }
    
    public int getMin() {
        if (minHead != -1) {
            return minArray[minHead];
        }
        return Integer.MIN_VALUE;
    }
}

코드설명

stack을 stack없이 array로 구현하는 방법이다.

먼저 생성자를 보면 기본값을 LIFO형태로 저장하는 array배열과 최소값을 저장하는 minArray배열을 만들었다.

생성자에서는 array와 minArray의 크기를 임의로 지정하였고, 인덱스인 head, minHead를 -1로 지정하였다.

 

push() 메소드는 기본적으로 array배열에 값을 저장한다. array배열의 크기보다 크면 오버플로가 발생한다.

이 때, val값을 minArray[minHead]과 비교하여 그 값이 작을때만 minArray배열에 같이 저장한다.

head가 처음값인 -1을 가리키고 있는 경우에는 무조건 minArray 배열 처음값에 값을 넣는다.

 

pop() 메소드에서는 기본적으로 array배열에서 값을 꺼낸다. head 인덱스가 0보다 작으면 언더플로가 발생한다.

이 때, 꺼낸 값을 minArray에 저장된 값과 비교하여 같다면 minHead 인덱스를 -1 해준다.

 

top() 메소드는 peek()메소드와 동일하므로 head 인덱스를 줄이지 않고 값만 꺼내온다.

 

getMin()메소드는 minHead 인덱스가 -1 이 아니라면 minArray값을 꺼내온다.

-1 이라면 MIN_VALUE를 꺼내온다.

 

시간복잡도 - O(1) (push,pop,top) O(min(m,n)) (getMin - m은 array 크기, n은 minArray)

공간복잡도 - O(n) (capacity * 4바이트 * 2)

 

문제를 풀며 생각한 흐름과 배운 점

수업에서 기존에 알고 있던 스택과 큐에 대해서 다시 배웠다.

그리고 마침 관련된 과제가 있어 stack을 배열만을 이용해서 구현해보기로 했다.

 

만약 stack을 그냥 기본 stack을 쓴다는 전제였다면 minArray가 아니라 minStack을 사용해서 값을 쉽게 넣고 빼고 했을 것이다.

그렇지만 기본 배열을 쓰기로 했으니 이 방법대로 풀어보기로 했다.

 

ArrayOutOfBound 발생을 방지하기 위해 여러가지 처리를 하는데 시간이 좀 소요되었다.

그런데 만들어놓고 보니 capacity가 너무 쓸데없이 큰 용량을 차지하고 있다는 생각이 들었다.

 

자바에서는 stack이 동적 배열이라 활용할 때에는 Stack을 직접 쓰는게 더 좋을 것 같다.

 

다른코드

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;
        }
    }
}

이 코드 또한 알고 있던 구현 방법이긴 한데 노드만을 사용한 것이 독특하다.

최소값과 value를 저장하는 노드를 만들어서 그 노드를 연결시키는 코드이다.

 

계속 노드를 생성하기 때문에 메모리가 커질 것 같은데, 내 코드와 비교하면 메모리 크기는 0.3mb 거의 차이가 없다.

(사실 내 코드도 특정 크기를 커버하기 위해 capacity가 커서 메모리를 쓸데없이 많이 잡아먹긴 한다.)

 

단 node에 들어가는 값이 최소값만이 아니라 다른 값들이 추가된다면 용량은 엄청 커지지 않을까 싶다.

 

정리

stack의 기본동작을 구현해보기

stack이 왜 필요한지 이해하기