[leetcode] 946. Validate Stack Sequences : https://leetcode.com/problems/validate-stack-sequences/

Validate Stack Sequences.cc

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        
        int N = pushed.size();
        
        vector<bool> check(N+1, false); // stack에 들어왔던 값인지 체크
        stack<int> s; // 스택
        int pushInd = 0; // push해야 할 인덱스

        for(int i=0;i<N;i++){
            int now = popped[i]; //pop해야 할 값
            
            if(!check[now]){ // 아직 stack에 들어온적이 없거나 이미 빠져나감.
                while(pushInd < N && pushed[pushInd] != now) { 
                    check[pushed[pushInd]] = true;
                    s.push(pushed[pushInd++]);
                }
                if(pushInd == N && now != N) return false; // 더이상 넣을 값이 없는데 pop할 값도 못찾을 경우
                pushInd++;
            }else{ //stack에 있음
                if(s.empty() || s.top() != now) return false; //다음에 pop할 값이 이번에 찾는 값이 아닌 경우
                s.pop();
            }   
        }
        
        return true;
    }
};