O(n²) Brute-force를 O(n) Sliding Window로 최적화한 알고리즘 설계

How I Learned to See the Matrix: Boosting My Problem‑Solving Speed Under Pressure

Timevolt2026년 6월 15일6분intermediate

AI 요약

Context

중첩 루프 기반의 Brute-force 접근법으로 인한 시간 복잡도 증가 문제 발생. 입력 데이터 규모 확대 시 연산 횟수가 기하급수적으로 증가하여 실시간 처리 성능 저하 및 타임아웃 위험 초래.

Two Pointers 기반의 Sliding Window 구조 채택을 통한 불필요한 재탐색 제거
Hash Map을 활용해 각 문자의 최신 인덱스를 저장함으로써 중복 문자 발견 시 즉각적인 상태 파악 구현
중복 문자 발견 시 left 포인터를 max(left, lastSeen[char] + 1)로 점프시켜 윈도우 범위를 최적화
단일 패스(Single Pass) 설계를 통해 모든 요소를 한 번만 방문하는 선형 시간 복잡도 달성
윈도우 유효성 검증 로직에 lastIndex.get(ch) >= left 조건을 추가하여 이전 윈도우 범위의 데이터를 배제하는 정밀 제어 적용

실천 포인트

최소 상태 유지(Minimal State)를 통해 윈도우 확장 가능 여부를 결정하는 설계 원칙 적용. 데이터 스트리밍이나 구간 합 계산 시 불필요한 전체 스캔 대신 포인터 이동과 상태 맵(State Map) 조합 검토.

태그