[LeetCode] 946. Validate Stack Sequences - 문제풀이

Description

주어진 배열의 순서대로 스택에 push, pop이 가능한지 여부를 반환하는 문제입니다.

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.

Constraints:

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• All the elements of pushed are unique.
• popped.length == pushed.length
• popped is a permutation of pushed.

Solution 1. Stack

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

      int len = pushed.length;
      int i = 0; // pushed index
      int j = 0; // popped index
      stack.push(pushed[i++]);
      
      while(!stack.isEmpty()){
          while(stack.peek() != popped[j]){
              if(i == len) return false;
              stack.push(pushed[i++]);
          }
          stack.pop(); // pop
          j++;
          if(stack.isEmpty() && i < len) stack.push(pushed[i++]);
      }

      return true    
    }

스택을 이용하여 popped의 요소와 일치하는 요소를 만날때까지 push해 준뒤 일치할경우 pop()을 해줍니다. 반복 중 스택의 peek값과 popped의 값이 달라 추가해야하는데 이미 모두 push된 상태라면 false를 반환해 줍니다.

Reference

Validate Stack Sequences - LeetCode