Min Stack

https://leetcode.com/problems/min-stack/description/

Min Stack - LeetCode

 

최소 값이 min 값을 원할 때 얻을 수 있는 Stack을 구현하는 문제이다. 클래스 안에 내부 배열을 선언하여 해결하였다. 문제를 풀고 찾아보니 Stack 클래스를 직접 이용해도 되는 문제였다. Java에서 제공하는 Stack과 PriorityQueue를 이용하는 방식이 더 쉽게 해결할 수 있을 것으로 예상한다.

 

우선 본인이 해결한 방식은 배열을 이용했으며, 문제 제약 조건에서 제공한 최대 명령 횟수를 이용하여 배열의 크기를 초기화 해주었다. 배열 크기가 그보다 작다면 push를 해당 횟수만큼 실행할 경우 배열을 넘어서게 될 것이기 때문이다.

 

0번 index부터 차례대로 넣어주었으며, 현재의 크기 curSize를 이용하여 스택의 최상단 위치를 체크하도록 하였다. 문제에서 요구하는 스택은 최소 값을 확인할 수 있어야 하며 O(n)의 시간 복잡도가 필요하다.

 

따라서 최소 값을 저장하는 배열도 하나 생성해주었다. push 또는 pop을 할 때 값을 찾고 인덱스를 순차적으로 밀어주거나, 땡겨 주어서 최소 값을 순서대로 정렬해서 저장하였다. 이 때 값을 찾는 index까지의 검색과 해당 index부터 마지막까지의 검색은 for 문을 한 번 순회하기 때문에 O(n)의 시간복잡도 제한 사항을 해결하였다. 순서대로 저장하였기 때문에 min[0]의 값은 현재 스택에 있는 최소 값을 확인할 수 있도록 하였다.

import java.util.*;  
  
class MinStack {  
  
    int[] arr;  
    int[] min;  
    int curSize;  
  
    public MinStack() {  
        arr = new int[3 * (int)Math.pow(10, 4)];  
        min = new int[3 * (int)Math.pow(10, 4)];  
        Arrays.fill(min, Integer.MAX_VALUE);  
        curSize = 0;  
    }  
  
    public void push(int value) {  
        arr[curSize] = value;  
        int minIdx = curSize;  
        for(int i = 0; i < curSize; i++){  
            if(value < min[i]){  
                minIdx = i;  
                break;  
            }  
        }  
  
        for(int i = curSize; i >= minIdx + 1; i--){  
            min[i] = min[i - 1];  
        }  
  
        min[minIdx] = value;  
  
        curSize++;  
    }  
  
    public void pop() {  
        curSize--;  
  
        int value = arr[curSize];  
        int minIdx = curSize;  
        for(int i = 0; i <= curSize; i++){  
            if(value == min[i]){  
                minIdx = i;  
                break;  
            }  
        }  
  
        for(int i = minIdx; i < curSize; i++){  
            min[i] = min[i + 1];  
        }  
  
    }  
  
    public int top() {  
        return arr[curSize - 1];  
    }  
  
    public int getMin() {  
        return min[0];  
    }  
}  
  
/**  
 * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(value); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */