본문으로 바로가기
반응형

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

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

반응형

댓글을 달아 주세요