[LeetCode] 946. Validate Stack Sequences

문제링크

스택에 push를 할 배열인 pushed와 스택에서 pop한 결과인 popped 배열이 주어졌을 때, popped 배열이 타당한 배열인지 여부를 반환하는 문제이다.

Ex) pushed=[1, 2, 3, 4, 5], popped=[4, 5, 3, 2, 1] 일 때

우선, 스택의 top이 pop해야 하는 숫자(== popped[0])와 같을 때까지 pushed에 있는 숫자들을 스택에 넣어 준다.

스택
4
3
2
1

현재 스택의 top은 4, popped[0]=4이므로 4를 pop해준다.

스택
3
2
1

현재 스택의 top은 3, popped[1]=5이므로 5를 stack에 push해준다.

스택
5
3
2
1

현재 스택의 top은 5, popped[1]=5이므로 5를 pop해준다.

이러한 과정을 반복하다가, popped 배열을 완전히 다 순회하면 true, 순회 중간에 pushed 배열을 넘어가버리면 false를 반환한다.

이를 코드로 작성하면 아래와 같다.

typedef struct stack_t {
    int items[1000];
    size_t top;
} stack_t;

void s_init(stack_t* s) {
    s->top=0;
}

void s_push(stack_t* s, int item) {
    s->items[s->top++]=item;
}

char s_pop(stack_t* s, int* res) {
    *res = s->items[--s->top];
    return 0;
}

int s_peek(stack_t *s, int* res) {
    if(s_is_empty(s)) {
        *res=NULL;
        return -1;
    }

    *res = s->items[s->top-1];
    return 0;
}

int s_is_empty(stack_t* s) {
    return s->top==0;
}

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
    stack_t stack;
    s_init(&stack);

    int i=0;

    for(int pop=0;pop<poppedSize;pop++)
    {
        int top;
        int res = s_peek(&stack, &top);

        if(res==-1) top = -1;

        while(popped[pop]!=top)
        {
            if(i==pushedSize)
            {
                return false;
            }
            s_push(&stack, pushed[i]);
            i+=1;
            res = s_peek(&stack, &top);
            if(res==-1) top = -1;
        }
        
        s_pop(&stack, &top);
        
    }

    return true;
}