HashMap 기반 Single Pass 설계로 Mirror Pair 탐색 시간 복잡도 O(N²)에서 O(N)으로 최적화

Context

배열 내 상호 역순인 Mirror Pair 간의 최소 거리를 산출하는 알고리즘 설계 필요. 중첩 루프를 이용한 Brute-force 방식 채택 시 데이터 규모 증가에 따른 O(N²)의 시간 복잡도로 인한 성능 저하 발생.

Technical Solution

• HashMap을 활용한 Single Pass 스캔 구조 설계를 통한 탐색 효율 극대화
• 현재 요소의 원본 값이 아닌 Reverse된 값을 Key로 저장하여 미래의 Mirror Pair를 선제적으로 매칭하는 전략 채택
• Reverse 연산을 Helper Method로 분리하여 32-bit 정수 범위 내 상수 시간 O(1) 처리 보장
• Map.containsKey()를 통한 기존 Mirror 후보 존재 여부 확인 및 즉각적인 거리 계산 수행
• 매 루프마다 최신 인덱스를 갱신 저장함으로써 최소 거리(Minimum Distance)를 효율적으로 유지하는 로직 구현