946. Validate Stack Sequences (Stack)

<아이디어>

실제 Stack을 바탕으로 시뮬레이션을 통해 가능한지 아닌지 확인 한다.

 poped의 첫 번째 값은 pushed에서 모든 값이 올 수 있지만

단 그 이후 poped의 값들은 pushed 배열에서 poped 배열에 첫 번 째로 온 값의

바로 전 값이거나 그 뒤에 있는 요소들이어야 한다.

 

<정답 코드>

import java.util.HashSet;
import java.util.Stack;

class Solution {
    // 시간 복잡도 O(n*n) 공간 복잡도 O(n)
    public boolean validateStackSequences(int[] pushed, int[] popped) {
//        pops의 첫번째 요소는 모든 요소가 오는 것 이 가능
//        pops의 두번째 요소는 처음 요소의 바로 앞 혹은 그 뒤에 오는 요소들 이어야 함
//        pops의 세번째 요소는 두번째 요소의 바로 앞 혹은 그 뒤에 오는 요소들 이어야 함
        // 실제 시뮬레이션 용 Stack
        Stack<Integer> pStack = new Stack<>();
        // 그 뒤에 오는 요소들 중 대상 요소를 빠르게 검사하기위한 Set
        HashSet<Integer> beforeUnits = new HashSet<>();
        // 첫 번째 요소를 찾았는지 확인할 변수
        boolean isFound = false;
        // 첫 변수의 pushed에서의 인덱스
        int firstIndex = 0;
        // stack과 set에 첫 번째 요소를 찾을 때 까지 채우기
        for (int i = 0; i < pushed.length; i++) {
            if(!isFound)
                pStack.add(pushed[i]);
            else
                beforeUnits.add(pushed[i]);
            if(pushed[i]==popped[0]) {
                firstIndex = i;
                pStack.pop();
                isFound = true;
            }
        }

        // 시뮬레이션 시작
        for (int i = 1; i < popped.length; i++) {
            // 바로 전 요소라면 pop
            int beforeValue = -1;
            if(!pStack.isEmpty())
                beforeValue = pStack.peek();

            if(beforeValue==popped[i]){
                pStack.pop();
                continue;
            }

            // 후속으로 존재하는 요소들 중에 pop 되어야 될 요소가 있다면
            else if(beforeUnits.contains(popped[i])){

                for (int j = firstIndex+1; j < pushed.length ; j++) {
                    // pushed의 이전 요소의 인덱스에서 다음으로 올 요소까지 push
                    pStack.add(pushed[j]);
                    // 만약 다음으로 pop되어야 할 요소를 찾았다면 pop 하고 이전요소(firstIndex)초기화
                    if(pushed[j]==popped[i]){
                        pStack.pop();
                        firstIndex=j;
                        break;
                    }
                }
            }
            else
                return false;
        }
        // 시뮬레이션이 마치고 스택이 비어 있으면 true 아니라면 false
        return pStack.isEmpty();
    }
}

 

<최적화>

class SolutionOtimal {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int N = pushed.length;
        Stack<Integer> stack = new Stack();

        int j = 0;
        for (int x: pushed) {
            stack.push(x);
            while (!stack.isEmpty() && j < N && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }

        return j == N;
    }
}

<메모> 

뭐든 단순하게 생각하고 하는게 좋을 것 같다.