[Leetcode] Validate Stack Sequences (#946)

 

 

문제 

 

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.

 

 

해설 코드 

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        stack = []
        j = 0
        for val in pushed:
            stack.append(val)
            # stack 에 원소가 존재하고 stack[-1] 이 popped[j] 와 같으면 stack을 pop 시킴
            while stack and stack[-1] == popped[j]:
                stack.pop()
                j += 1
        # stack이 비면 false 인데 여기서는 비어야 true 이기 때문에 not을 붙여줌
        return not stack

분석 > while 문을 작성할 때는 항상 조건을 꼼꼼히 적는 연습을 하자. 그리고 이 문제를 통해 return not 이라는 개념을 알게 되었다. 그리고 popped 배열도 같이 pop 하지 않아도 j 를 증가시킴으로써 비교할 수 있다는 것도 새롭게 알게 되었다.