[코딩인터뷰 완전정복] 3.2 스택 Min

Q : 기본적인 push와 pop 기능이 구현된 스택에서 최솟값을 반환하는 min함수를 추가하려고 한다. 어떻게 설계할 수 있겠는가?

push, pop, min 연산은 모두 O(1) 시간에 동작해야 한다.

#include <iostream>

class stack {
private:
    int *start;
    int nOfE;
    int size;

    int *minStack;
    int minNofE;
    int minStackSize;
public:

    stack() {
        start = new int[10];
        nOfE = 0;
        size = 10;

        minStack = new int[10];
        minNofE = 0;
        minStackSize = 10;
    }

    stack(int N) {
        start = new int[N];
        nOfE = 0;
        size = N;

        minStack = new int[N];
        minNofE = 0;
        minStackSize = N;
    }

    void push(int n) {
        if (nOfE == size) {
            int *sizeIncreaseStack = new int[size * 2];
            sizeIncreaseStack = start;
            for (int i = 0; i < size; i++) {
                sizeIncreaseStack[i] = start[i];
            }
            start = sizeIncreaseStack;
            size *= 2;
        }
        start[nOfE] = n;

        if (minNofE == 0) {
            minStack[0] = n;
            minNofE++;
        }
        else if(minStack[minNofE-1] >= n){
            
            minStack[minNofE] = n;
            minNofE++;

        }

        nOfE++;
    }

    int pop() {
        if (nOfE == 0) return NULL;
        nOfE--;

        if (start[nOfE] == minStack[minNofE-1]) {
            minNofE--;
        }

        return start[nOfE];
    }

    int Size() {
        return nOfE;
    }

    int Min() {
        if (minNofE == 0) return NULL;
        return minStack[minNofE - 1];
    }
};

기본 스택에 Min 값을 저장하는 스택을 추가하여 push값이 Min보다 작으면 스택에 해당 값을 추가 시켜준다.

pop값이 Min값과 같으면 Min스택에서 해당 값을 제거한다.

이렇게 하면 push(), pop(), min() 모두  O(1)에 처리 할 수 있다.