이진 리스트가 하나 주어졌을 때, 1은 push(삽입) 연산을, 0은 pop(삭제) 연산을 의미한다고 가정해 봅시다. 이때 우리가 확인해야 할 것은 이 연산 시퀀스 전체가 유효한지, 즉 실행 도중 빈 스택이나 빈 큐에서 요소를 꺼내는 상황이 발생하지 않는지 판단하는 것입니다.
문제 예시
예를 들어 입력이 nums = [1,0,1,1,0,1]이라면, 이 시퀀스는 [Push, Pop, Push, Push, Pop, Push] 순서로 해석됩니다. 각 시점에서 삭제할 요소가 항상 존재하므로 출력 결과는 True가 됩니다.
반대로 리스트가 비어 있는 상태에서 pop 연산이 등장하면 그 시퀀스는 유효하지 않으므로 False를 반환해야 합니다.
해결 접근 방법
이 문제는 카운터 하나만으로 간단하게 해결할 수 있습니다.
- push_count 변수를 0으로 초기화합니다.
- 리스트를 처음부터 끝까지 순회하면서 다음을 반복합니다.
- 현재 값이 1(push)이면 push_count를 1 증가시킵니다.
- 현재 값이 0(pop)이면 push_count를 1 감소시킵니다.
- 순회 중 push_count가 음수가 되면, 존재하지 않는 요소를 꺼내려 한 것이므로 즉시 False를 반환합니다.
- 모든 연산을 통과했다면 True를 반환합니다.
핵심 아이디어는 push_count가 현재 저장된 요소의 개수를 나타낸다는 점입니다. 이 값이 0보다 작아지는 순간 유효하지 않은 연산이 발생한 것입니다.
구현 코드
def solve(nums):
push_count = 0
for i in range(len(nums)):
if nums[i]:
push_count += 1
else:
push_count -= 1
if push_count < 0:
return False
return True
nums = [1,0,1,1,0,1]
print(solve(nums))입력
[1,0,1,1,0,1]
출력
True
복잡도 분석
리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가로 사용하는 공간은 정수 변수 하나뿐이므로 공간 복잡도는 O(1)입니다.