[Java] 155. Min Stack

문제 파악

O(1) 시간 복잡도로 해당 메서드 들을 동작할 수 있도록 구현해야한다.

 

---

풀이

 

1️⃣ Stack 클래스 이용

위 문제에서, 가장 중요한 메서드는 getMin() 메서드이다.

 

다른, push(), pop(), top() 메서드는 기존 Stack 클래스에서도 O(1) 에 수행할 수 있기 때문이다.

 

따라서, 스택에 요소를 삽입할 때, 최솟값을 저장하고 getMin() 메서드를 호출할 때 바로 반환할 수 있도록 해야 O(1)을 만족할 수 있을 것이다.

 

최솟값을 저장하는 스택을 따로 추가해서, 값을 push 할때마다 해당 위치의 스택 값까지의 최솟값을 기록하도록 구현하였다.

 

import java.util.*;
class MinStack {

    Stack<Integer> stack;
    Stack<Integer> stackForMin;

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

 

결과

 

2️⃣ 배열과 포인터를 이용한 방식

자바에서 제공하는 스택 클래스가 아닌 배열과 포인터를 이용해서 구현해보았다.

 

최대 30000번 메서드를 호출한다고 하였으므로, 배열의 크기를 30001로 설정한 뒤

 

push, pop에 따라 pointer를 변경시켜주는 방식이다.

 

최솟값을 유지하는 방법은 1번 풀이와 동일한 방식을 사용했다.

 

class MinStack {
    int[] stack;
    int[] stackForMin;
    int pointer = -1;

    public MinStack() {
        stack = new int[30001];
        stackForMin = new int[30001];
    }
    
    public void push(int val) {
        pointer++;
        stack[pointer] = val;

        if(pointer==0){
            stackForMin[pointer] = val;
        }else{
            stackForMin[pointer] = Math.min(stackForMin[pointer-1],val);
        }

    }
    
    public void pop() {
        pointer--;
    }
    
    public int top() {
        return stack[pointer];
    }
    
    public int getMin() {
        return stackForMin[pointer];
    }
}

 

결과

 

스택 자료구조를 사용한 방식보다 낮은 메모리와 빠른 실행 시간이 되었다.

 

---

📖 회고

스택에서 가장 최솟값을 반환하라는 메서드를 추가하라는 문제가 있을 것이라고 상상하지 못했다.

 

하지만 알고리즘 강의 때, 들었던 아이디어를 바탕으로 쉽게 구현할 수 있었다.