[JavaScript] 946. Validate Stack Sequences 쉬운설명

946. Validate Stack Sequences

 

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

 

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2: 

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

 

 

계획

문제 해결 전략

 

hashmap을 이용하면 편하겠지만, 스택을 이용해서 풀어보려합니다. 

 

먼저 스택에 pushed array에 값을 앞에서부터 하나씩 넣어주면서, 넣어주는 값이 popped에 첫번째 값과 같은게 나올때까지 계속 넣어줍니다. 

 

만약 같은값이라면, stack에서 pop해주고, popped에 다음값이랑 stack에서 가장 위에 위치한 값이랑 또 같은지확인합니다. 

 

다르다면, 다시 pushed를 stack에 넣어주는것을 반복하고 만약 다시 같다면, stack에서 pop하고 popped의 다음값과 stack에 가장 위에 위치한 값이랑 같은지 확인하고 이 과정을 반복합니다. 

 

이 반복문이 끝나면, 모두 제거되었는지 확인하기위해 length를 체크합니다. 

 

lengh가 0이상이면, false 0이면 true를 리턴합니다. 

 

 

 

 

해설

let validateStackSequences = function (pushed, popped) {
      let stack = [pushed[0]];
        
      let i = 1; // index for pushed
      let j = 0; // index for popped
      while (i < pushed.length || j < popped.length) {
          console.log(stack)
          
        if (stack[stack.length - 1] == popped[j]) {
            stack.pop();
            j++;
        
        } else {
            
            if (i < pushed.length) {
                stack.push(pushed[i++])
            }
            else {
                return false;
            }
      }
      return true;
};