Intuition

pushed의 원소들을 stack에 push하면서 popped의 원소들과 비교해본다.

Approach

예시를 들어보겠다. sp는 stack pointer, pushp와 popp는 각각 push pointer, pop pointer다.1,2,3은 popp의 4와 일치하지 않으므로 모두 stack에 push해준다.이 다음 4까지 push를 해주고나면,popp의 4와 일치하기 때문에 stack에서 4를 pop해주고, popp도 +1시켜준다. 이런식으로 popp이 popped배열의 끝까지 도달한다면, 두 배열이 stack으로 구현 가능함을 의미한다.

Solution

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize) {
    int arr[1000];
    int sp=0;
    int pushp=0;
    int popp=0;

    while (pushp<pushedSize){
        arr[sp++]=pushed[pushp++];

        while (sp>0&&arr[sp-1]==popped[popp]){
            sp--;
            popp++;
        }
    }

    return popp==poppedSize;
}

Time Complexity

push와 pop의 모든 동작을 합쳐도 결국에 두 배열의 크기만큼인 2N이다.
따라서, $O(N)$

맞는지 모르겠다

지적 및 질문 환영