Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

파이썬에서 주어진 푸시 팝 시퀀스가 ​​적절한지 확인하는 프로그램

<시간/>

푸시라고 하는 숫자 목록과 팝이라고 하는 또 다른 숫자 목록이 있다고 가정하면 이것이 스택 푸시 및 팝 작업의 유효한 시퀀스인지 여부를 확인해야 합니다.

따라서 입력이 pushs =[1, 2, 5, 7, 9] pops =[2, 1, 9, 7, 5]인 경우 [1, 2]를 누를 수 있으므로 출력은 True가 됩니다. 먼저 둘 다 터트립니다. 그런 다음 [5, 7, 9]를 누르고 모두 터뜨립니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • s :=새 스택
  • i :=0
  • 푸시의 각 요소에 대해 다음을 수행합니다.
    • ele을 s로 푸시
    • 크기가 s> 0이고 pops[i]가 s의 최상위 요소인 경우 do
      • s에서 최상위 요소 삭제
      • 나는 :=나는 + 1
  • s의 크기가 0과 같으면 true를 반환하고, 그렇지 않으면 false를 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, pushes, pops):
      s = []
      i = 0

      for ele in pushes:
         s.append(ele)

         while len(s) > 0 and pops[i] == s[-1]:
            s.pop()
            i += 1

      return len(s) == 0

ob = Solution()
pushes = [1, 2, 5, 7, 9]
pops = [2, 1, 9, 7, 5]
print(ob.solve(pushes, pops))

입력

[1, 2, 5, 7, 9], [2, 1, 9, 7, 5]

출력

True