946. Validate Stack Sequences

https://leetcode.com/problems/validate-stack-sequences/

Validate Stack Sequences - LeetCode

 

스택을 이용하여 풀 수 있는 문제이다.
pushed 리스트가 있을때, 0번 인덱스는 stack에 넣어준다.

for문을 얼마정도까지 돌릴 것인가 생각했을 때,
최대로 pushed 리스트와 popped의 리스트의 길이의 합만큼 일어난다고 생각했다.

 

그래서 len(pushed) + len(popped)로 표현하였다.

 

그리고 stack의 top이 popped의 맨 앞 원소와 일치하면 

stack의 마지막 원소를 제거해주고,

popped의 첫번째 원소를 제거해준다. (일치하면 계속 제거)

 

그리고 pushed가 존재하면 iteration한번 돌때마다 원소를 stack에 추가해준다.

 

마지막에 true false판별은

stack, popped, pushed가 빈 리스트인 경우에는 올바르게 다 제거되었으므로 true

 

그 외에는 모두 false로 리턴한다.

 

 

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """

        stack = []

        if len(pushed)==0 and len(popped)==0:
            return True

        # fisrt step
        first_data = pushed.pop(0)

        stack.append(first_data)
        for i in range(0, len(popped)+len(pushed), 1):

            # pop continuously
            while True:
                if len(popped) > 0:
                    if len(stack) > 0:
                        if stack[-1] == popped[0]:
                            stack.pop()
                            popped.pop(0)
                        else:
                            break
                    else:
                        break
                else:
                    break

            if pushed:
                stack.append(pushed.pop(0))

        #print(pushed, popped, stack)
        if not pushed and not popped and not stack:
            return True

        return False