Two Stacks 구조를 통한 getMin() 연산의 O(1) 시간 복잡도 달성

Context

일반적인 Stack 구조에서 최솟값을 찾기 위해 전체 요소를 순회하는 Brute Force 방식의 한계 존재. 이로 인해 getMin() 호출 시 O(N)의 시간 복잡도가 발생하여 대규모 데이터 처리 시 성능 병목 지점으로 작용.

Technical Solution

• 데이터 저장용 Main Stack과 최솟값 추적용 Min Stack을 분리한 이중 스택 구조 설계
• 새로운 요소 Push 시 현재 Min Stack의 Top 값과 비교하여 최솟값 갱신 시에만 Min Stack에 추가하는 조건부 저장 로직 적용
• Pop 연산 시 Main Stack의 제거 대상이 Min Stack의 Top과 일치하는지 확인하여 동기화된 제거 수행
• Min Stack의 Top을 항상 현재 스택의 최솟값으로 유지함으로써 탐색 과정 없는 즉시 반환 구조 구현
• 공간 복잡도를 희생하여 시간 복잡도를 최적화한 Trade-off 전략 채택