Leetcode - 155. Min Stack

문제

다음동작의 stack을 구현하라. 단 getMin()함수의 시간복잡도는 상수시간이어야한다.

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

아이디어

• getMin() 함수가 문제인데, 무지성으로 생각하면 모든 스택값을 리니어하게 탐색하면 된다. 그러면 O(1)을 만족할 수 없다.
• heap 자료구조를 추가로 사용해야하나 생각이 들었다. 시간복잡도는 만족할수 있을것. 그런데 stack에서 pop을하면 heap자료구조는 어떻게 변경해야하는지? indexed heap을 사용해야하나? 구현에 너무 복잡도가 올라간다.
• 힌트를 참고했는데, 스택의 각 요소마다 최소값을 가지면 된다는것이었다!(천재적 아이디어...) 스택의 구조를 생각해보면 계속해서 위로 샇인다. 쌓을때마다 top의 요소는 그 아래의 min값과 비교해서 더 작은 값을 min값으로 가지면 된다. 그리고 getMin()은 stack[top].min 을 리턴하면 끝이다.

해결

struct elem에 val뿐만아니라 min값을 멤버로 추가한다. 이 구조체를 스택으로 만들고 push할때마다 min도 업데이트 한다.
그냥 배열을 30001개를 때려박았는데, 더 효율적으로 하려면 realloc()을 사용해 동적으로 배열의 크기를 늘리면 될것같다. (참고 -> realloc 으로 C++ 의 vector구현하기). 만약 c++로 풀었다면 vector의 push_back을 사용하면 되니 구현이 훨씬 간단했을것 같다.

암튼 아주 재미있는 문제였다.

struct elem {
    int val;
    int min;
};

typedef struct {
    struct elem *arr;
    int top;
    int size;
} MinStack;

MinStack* minStackCreate() {
    MinStack *s = malloc(sizeof(MinStack));
    s->size = 30001;
    s->arr = (struct elem *)calloc(s->size, sizeof(struct elem));
    s->top = -1;
    return s;
}
#define min(a,b) (((a) < (b)) ? (a): (b))
void minStackPush(MinStack* obj, int val) {
    if (obj->top == obj->size) {
        fprintf(stderr, "stack is full\n");
        return;
    }
    obj->top++;
    int top = obj->top;
    obj->arr[top].val = val;
    if (top == 0) {
        obj->arr[top].min = val;
    } else {
        obj->arr[top].min = min(val, obj->arr[top-1].min);
    }
}

void minStackPop(MinStack* obj) {
    if (obj->top == -1) {
        fprintf(stderr, "stack is empty\n");
        return;
    }
    obj->top--;  
}

int minStackTop(MinStack* obj) {
    return obj->arr[obj->top].val;  
}

int minStackGetMin(MinStack* obj) {
    return obj->arr[obj->top].min;  
}

void minStackFree(MinStack* obj) {
    free(obj->arr);
    free(obj);
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, val);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackGetMin(obj);
 
 * minStackFree(obj);
*/