숫자 리스트 pushes와 또 다른 숫자 리스트 pops가 있다고 가정해 보겠습니다. 이때 두 리스트가 실제 스택(Stack)에서 수행 가능한 유효한 푸시(push)·팝(pop) 연산 순서인지 확인해야 합니다.
예를 들어 입력이 pushes = [1, 2, 5, 7, 9], pops = [2, 1, 9, 7, 5]라고 한다면 결과는 True입니다. 먼저 1과 2를 차례로 푸시한 뒤 두 요소를 모두 팝하고, 이어서 5, 7, 9를 푸시한 후 역순으로 모두 팝하면 되기 때문입니다.
문제 해결 접근 방식
이 문제는 실제 스택을 하나 만들어 시뮬레이션하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 새로운 빈 스택 s를 생성하고, 팝 인덱스 i를 0으로 초기화합니다.
- pushes의 각 요소를 순서대로 스택에 푸시합니다.
- 요소를 푸시할 때마다 스택이 비어 있지 않고, pops[i]가 스택의 최상단(top) 요소와 일치하는 동안 반복해서 팝을 수행하고 i를 1씩 증가시킵니다.
- 모든 푸시 작업이 끝난 후 스택이 완전히 비어 있다면 유효한 시퀀스이므로 true를 반환하고, 남은 요소가 있다면 false를 반환합니다.
즉, 팝 순서가 스택의 LIFO(Last-In-First-Out) 특성과 맞아떨어지는지 검증하는 과정이라고 볼 수 있습니다.
파이썬 구현 예제
위 알고리즘을 파이썬으로 구현하면 다음과 같습니다.
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))
코드 동작 원리
s.append(ele): 리스트를 스택처럼 사용해 요소를 푸시합니다.s[-1]: 스택의 최상단(마지막) 요소에 접근합니다.s.pop(): 최상단 요소를 제거하여 팝 연산을 수행합니다.- 내부 while 루프 덕분에 푸시 직후 연속적으로 여러 번 팝이 가능해, 중간에 삽입되는 팝 순서도 정확히 처리됩니다.
입력
[1, 2, 5, 7, 9], [2, 1, 9, 7, 5]
출력
True
복잡도 분석
각 요소는 최대 한 번 푸시되고 한 번 팝되므로, 시간 복잡도는 O(n), 공간 복잡도 역시 스택 저장을 위해 O(n)입니다. 여기서 n은 pushes 리스트의 길이입니다.