Min Stack (Stack)

이번 문제는 LeetCode의 Queue, Stack 튜토리얼에 포함되어 있던 문제로 스택의 기본적인 연산과 추가적으로 요구되는 연산을 수행할 수 있는 스택 자료구조를 직접 구축하여 풀어보는 것이 목적이다.

Explore - LeetCode

재밌는 것은 상위권 풀이를 보면 자바에서 제공하는 Stack 자료구조를 이용해 푼 풀이가 많다는 것이다. Stack 자료구조에 대한 이해를 위해 직접 스택을 만들어서 풀어보는 게 목적인데 내장 Stack 자료구조를 사용해서 문제를 풀고 있으니 대체 뭔 의미가 있나 싶다. 단순히 통계에서 상위권에 위치하는 걸 원하는 거라면 또 모르겠지만...

 

어쨌든 문제에서 요구하는 스택 자료구조는 다음과 같은 기능을 제공해야 한다.

• push(x): 스택에 x를 삽입한다.

• pop(): 스택의 맨 위 요소를 삭제한다.

• top(): 스택의 맨 위 요소를 삭제하지 않고 반환한다.

• getMin(): 스택에서 가장 작은 값을 반환한다.

위의 3가지 기능은 일반적으로 스택에 요구되는 기능이지만 특이하게 getMin()이라는 메서드에서는 스택에서 가장 작은 값을 찾아서 반환하는 기능이 요구된다. 기본적으로는 List 인터페이스를 구현한 ArrayList 자료구조를 사용하여 스택을 구축할 수 있을 텐데 ArrayList 자체적으로 크기를 재는 메서드나 특정 위치의 요소를 가져올 수 있는 메서드를 제공하기 때문에 충분히 스택을 구현할 수 있다.

 

중요한 것은 getMin() 메서드를 구현하는 것인데 이는 어떻게 할 수 있을까? 제일 쉬운 방법은 스택의 모든 값을 탐색해서 가장 작은 값을 찾는 것이다.

    public int getMin() {
        int minValue = Integer.MAX_VALUE;
        for(int index=0;index<stack.size();index++){
            if(stack.get(index) < minValue){
                minValue = stack.get(index);
            }
        }
        return minValue; 
    }

위의 메서드처럼 내부적으로 구현된 Stack 자료구조인 stack에 대하여 하나씩 값을 꺼내서 비교해보면서 최솟값을 찾아서 반환해주는 것이 일반적으로 생각해볼 수 있는 방법인데 이 경우 매 호출마다 스택에 있는 값들을 전부 확인해야 하기 때문에 성능이 좋지 않다. 그래서 매 호출마다 비교하는 게 아니라 스택에 데이터가 삽입, 삭제될 때마다 최솟값을 실시간으로 업데이트하는 개선 방안을 생각해볼 수 있다.

예를 들어 위와 같은 스택이 있다고 할 때 최솟값을 실시간으로 업데이트한다면 삽입 연산에서는 새로 삽입된 값과 기존의 최솟값을 비교하여 새로운 최솟값을 구하는 로직이 추가되어야 한다. 일단 비어있는 스택에 5를 삽입했을 경우 기존의 최솟값(Integer.MAX_VALUE)과 5를 비교하면 당연히 5가 더 작기 때문에 스택의 최솟값(그림에서는 아래의 회색 정사각형)을 5로 업데이트하고 최솟값 후보 리스트(그림에서는 왼쪽의 긴 회색 직사각형)에 이 최솟값이 삽입된 스택의 위치를 기억한다. 이때 스택의 위치를 기억하는 리스트는 마찬가지로 스택으로 구현하면 좋다. 왜 최솟값이 삽입된 스택의 위치를 기억해야 하는 것일까? 이는 스택에서 요소가 삭제될 때 최솟값을 업데이트하기 위해서다.

위의 로직을 반영하여 위처럼 스택에 5, 9, 12, 7, 3, 6, 10, 1을 삽입했다면 최종적으로 스택의 최솟값은 1이 된다. 그리고 삽입 연산에서 최솟값이 갱신될 때마다 리스트에 추가했던 최솟값 후보 리스트에 0, 4, 7이 등록된 것을 볼 수 있는데 이는 맨 처음에 인덱스 0에 삽입된 최솟값 5, 그리고 인덱스 4에 삽입된 새로운 최솟값 3, 그리고 인덱스 7에 삽입된 새로운 최솟값 1이 순차적으로 리스트에 등록된 것이다. 여기서 만약 pop() 연산을 통해 인덱스 7에 있는 현재 최솟값 1을 삭제하면 어떻게 해야 할까?

현재 삭제된 값 1은 인덱스 7이고 이는 인덱스가 최솟값 후보 리스트에 포함되어 있는 최솟값이기 때문에 리스트에서도 해당 인덱스를 삭제해야 한다. 그리고 가장 최근의 최솟값 후보, 만약 스택으로 구현되어 있다면 스택의 가장 위에 있는 값을 최솟값의 인덱스로 생각해서 이전의 최솟값으로 되돌아가는 것이다. 위의 그림에서는 0, 4, 7이 최솟값 후보 리스트에 포함되어 있었는데 스택에서 현재 최솟값인 1이 삭제되었기 대문에 리스트에서도 인덱스 7이 삭제되어 0, 4가 된다. 그래서 리스트의 가장 뒤(스택의 top)에 있는 인덱스 4에 위치한 값(3)이 새로운 최솟값이 된다. 이는 최솟값 변경 기록을 저장해놨다가 최솟값 요소가 삭제될 때마다 Ctrl + Z 하는 느낌으로 생각하면 된다.

그렇다면 스택에서 모든 값이 삭제되어 최솟값도 없다면 어떻게 처리해줘야 할까? 스택의 동작 자체는 스택 자료구조에서 빈 스택에 대해 삭제 연산을 수행하지 않도록 예외를 설정해줘야 한다. 다행히 문제에서는 빈 스택에는 삭제 연산을 하지 않는다고 명시되어 있기 때문에 따로 처리해줄 필요는 없지만 최솟값이 모두 삭제되었을 경우 다시 처음부터 비교하기 위해 스택의 최솟값을 Integer.MAX_VALUE로 설정해 줄 필요가 있다. 그래야 스택에 들어오는 값을 새로운 최솟값으로 설정하여 진행할 수 있기 때문이다.

 

이를 반영하여 작성한 코드는 다음과 같다.

import java.util.List;
import java.util.ArrayList;

class MinStack {
    private List<Integer> stack = new ArrayList<Integer>();
    private List<Integer> minValueIndex = new ArrayList<Integer>();
    private int minValue = Integer.MAX_VALUE;

    /** initialize your data structure here. */
    public MinStack() {
        
    }
    
    public void push(int x) {
        stack.add(x);
        if(x <= minValue){
            minValueIndex.add(stack.size() - 1);
            minValue = x;
        }
    }
    
    public void pop() {
        int deletingIndex = stack.size() - 1;
        if(minValueIndex.get(minValueIndex.size() - 1) == deletingIndex){
            minValueIndex.remove(minValueIndex.size() - 1);
            if(minValueIndex.size() > 0){
                minValue = stack.get(minValueIndex.get(minValueIndex.size() - 1));
            } else {
                minValue = Integer.MAX_VALUE;
            }
        }
        stack.remove(deletingIndex);
    }
    
    public int top() {
        return stack.get(stack.size() - 1);
    }
    
    public int getMin() {
        return minValue;
    }
}

스택의 마지막 요소를 참조하느라 stack.size() - 1 같은 표현식이 많이 들어가 있는데 이는 가독성을 생각한다면 따로 변수로 빼는 것도 괜찮을 것 같다. 어쨌든 중요한 것은 삭제 연산이 수행될 때마다 최솟값이 삭제된다면 저장한 최솟값 리스트에서 새로운 최솟값을 꺼내서 불러오고 다 꺼냈다면 Integer.MAX_VALUE를 최솟값으로 설정해두고 있다는 것이다. 빈 스택에 대하여 getMin() 메서드를 호출하면 이 최댓값 상수를 반환하기 때문에 문제가 되겠지만 문제에서 그 부분을 처리하는 것은 요구되지 않았다.

스택을 활용하지 않고 매번 탐색을 통해 최솟값을 찾는 결과와 스택을 활용하여 최솟값을 찾는 결과를 비교하면 위와 같다. 속도가 약 99배의 차이가 나는 것을 볼 수 있다. 상황에 맞는 적절한 자료구조 선택의 중요성을 다시금 느낄 수 있다.

 

되돌리기 작업인 Ctrl + Z가 기본적으로 스택을 활용한 기능이기 때문에 그와 비슷하게 생각하면 이해하기 어렵지 않을 것이다. 새로운 최솟값이 저장될 때마다 되돌리기 목록에 쌓아뒀다가 스택에서 요소가 삭제되면서 최솟값도 삭제됐다면 되돌리기 목록에서 다시 하나씩 꺼내서 최솟값을 복구하는 것이다.