[LeetCode] 946 | Validate Stack Sequences | Python

---

문제 링크: https://leetcode.com/problems/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.

---

조건

• 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.

---

내 풀이

pushed 리스트 앞 원소부터 차례로 stack에 넣으면서 pushed에서는 삭제한다.

pushed의 맨 앞 원소가 popped의 맨 앞 원소와 일치하면 넣자마자 빼야하므로 둘 다 각각 pushed와 popped 리스트에서 삭제한다.

이어지는 popped의 맨 앞 원소가 stack의 맨 뒤 원소와 일치한다면 stack에서 pop하고, popped에서 삭제한다.

위 과정을 pushed 리스트가 빌때까지 진행한다.

 

이제 남아있는 것은 popped 리스트다.

stack 리스트는 맨 뒤부터, popped 리스트는 맨 앞부터 비교하면서, 일치한다면 stack에서 pop한다.

만약 일치하지 않다면 pop할 수 없으므려 False를 리턴하면 된다.

---

코드

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        while pushed:
            while pushed and popped and popped[0] != pushed[0]:
                stack.append(pushed[0])
                del pushed[0]
            del popped[0]
            
            if pushed:
                del pushed[0]
            
            while stack and stack[-1] == popped[0]:
                stack.pop()
                del popped[0]
        
        while popped:
            if popped[0] == stack.pop():
                del popped[0]
            else:
                return False
        
        return True