[Leetcode Top Interview 150] 155. Min Stack

난이도 : medium

문제링크

• push, pop, top, getMin 메서드를 구현하라
• 모든 메서드의 시간 복잡도는 O(1)여야 함
• 2^(-31) <= val <= 2^31 -1

 

1. 접근법

• 배열을 가지고 구현하기
• top 인덱스를 두어 LIFO를 구현한다
  • push, pop, top 구현
• getMin()
  • push, pop될 때마다 val 뿐만 아니라 해당 인덱스에 인덱스까지의 최소값을 저장

 

2. 의사코드

    public MinStack() {
     	top = -1   
        arr : 30000 개 짜리 정수형 배열 선언
        min : 30000 개 짜리 정수형 배열 선언
    }
    
    public void push(int val) {
        top 하나 증가
        arr[top] : val 값 삽입;
        min[top] : min(val, min[top-1]) 값 삽입;
    }
    
    public void pop() {
        top--;        
        min[top] = arr[val], min[top-1] 중에 작은 값으로 갱신;
    }
    
    public int top() {
        return arr[top];
    }
    
    public int getMin() {
        return min[top];
    }

 

 

3. 구현 코드

class MinStack {
    private int[] arr;
    private int[] min;
    private int top;

    public MinStack() {     	
        arr = new int[30000];
        min = new int[30000];
        top = -1;
    }
    
    public void push(int val) {
        top++;
        arr[top] = val;
        min[top] = top == 0 ? val : Math.min(val, min[top-1]);
    }
    
    public void pop() {
        top--;
    }
    
    public int top() {
        return arr[top];
    }
    
    public int getMin() {
        return min[top];
    }
}

• 문제에서 적어도 30000번 호출하여 테스트한다 하였으므로 스택의 크기를 30000으로 초기화
• push시 arr, min 배열 갱신
  
  • 새로 들어오는 값과 min[top-1] 값을 비교하여 더 작은 값을 min[top]에 할당

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(1) - 반복문 없음
• 공간복잡도 : O(1) - 상태변수만 선언되어 있음

 

5. 개선점

공간 복잡도를 개선해서 풀수 있을까... 생각이 나질 않는다

 

6. 회고

private Stack<Integer> stack;
private Stack<Integer> min_stack;

MinStack() {
    stack = new Stack<>();
    min_stack = new Stack<>();
}

public void push(int val) {
    if (min_stack.isEmpty() || min_stack.peek().intValue() >= val) {
        min_stack.push(val);
    }

    stack.push(val);
}

public void pop() {
    if (stack.peek().equals(min_stack.peek())) {
        min_stack.pop();
    }

    stack.pop();
}

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

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

(출처 : NickWhite)

• 자바의 Stack 클래스를 활용하여 짜는 방법
• push : min_stack이 비어있거나 기존의 min_stack의 맨위값이 새로 들어오려는 값보다 큰 경우
• pop : min_stack의 맨위값이 나가려는 값과 같을 경우 

검증 로직에 참일때만 min_stack의 push, pop 작업이 일어나므로 

min_stack의 맨 위값은 현재 stack의 최소값과 같음

 

LIFO는 하나씩, 맨 위에서만 연산이 이루어지는 점 을 이용했다