푸시라고 하는 숫자 목록과 팝이라고 하는 또 다른 숫자 목록이 있다고 가정하면 이것이 스택 푸시 및 팝 작업의 유효한 시퀀스인지 여부를 확인해야 합니다.
따라서 입력이 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