Monotonic Stack 도입으로 배열 탐색 시간 복잡도 O(n²)에서 O(n)으로 단축

Context

배열 내 특정 조건을 만족하는 인접 요소를 찾는 과정에서 중첩 루프를 활용한 Brute-force 방식 사용. 데이터 규모 증가에 따른 Time Limit Exceeded 발생 및 연산 반복으로 인한 성능 병목 지점 확인.

Technical Solution

• 요소 간의 단조 관계를 유지하는 Monotonic Stack 구조 설계
• 스택 내에 인덱스를 저장하여 이전 요소의 조건을 충족하는 시점을 즉각적으로 파악
• 새로운 요소가 스택 상단 값의 단조성을 깨뜨리는 순간을 '정답 발견 시점'으로 정의하여 Pop 수행
• 각 인덱스가 스택에 한 번 Push되고 최대 한 번 Pop되는 선형 처리 구조 채택
• Next Greater/Smaller 등 문제 요구 조건에 따른 비교 연산자 및 스캔 방향 최적화
• Sentinel 값을 추가하여 루프 종료 후 스택에 남은 잔여 데이터의 일괄 처리 보장