Merge Sort 기반의 Two-Pointer 전략을 통한 O(N²)에서 O(N log N)으로의 성능 최적화

Reverse Pairs

Jaspreet singh2026년 6월 6일5분intermediate

AI 요약

Context

배열 내 i < j 및 nums[i] > 2 * nums[j] 조건을 만족하는 Reverse Pairs를 탐색하는 문제. 모든 쌍을 개별적으로 검증하는 Brute Force 방식은 데이터 규모 증가에 따라 시간 복잡도가 급격히 상승하는 한계 존재.

분할 정복(Divide and Conquer) 기반의 Merge Sort 구조를 채택하여 배열을 정렬된 상태로 유지하는 설계
Merge 단계 직전에 Two-Pointer 전략을 도입하여 Left 및 Right Sorted Halves 간의 조건 만족 쌍을 선형 시간 내에 계산
Right Half가 정렬되어 있다는 특성을 활용해 특정 요소가 조건을 만족하면 그 이전의 모든 작은 요소들도 자동으로 조건을 만족함을 이용한 연산 최적화
Counting 단계와 Merge 단계를 엄격히 분리하여 정렬로 인해 데이터의 상대적 위치 정보가 손실되기 전으로 연산을 배치
(long) 캐스팅을 통한 Integer Overflow 방지로 데이터 무결성 확보

실천 포인트

1. 데이터의 상대적 순서 유지와 정렬이 동시에 필요한 경우 Merge Sort 변형 적용 검토

2. Two-Pointer 적용 전 데이터가 정렬 상태인지 확인하여 시간 복잡도 O(N) 달성 가능 여부 판단

3. 곱셈 연산이 포함된 비교 조건에서 데이터 타입의 범위를 초과하는 Overflow 가능성 체크

태그