피드로 돌아가기
Dev.toBackend
원문 읽기
O((m+n)log(m+n))에서 O(m+n)으로의 시간 복잡도 최적화
Leetcode 150 | Day 1: Merge Sorted Array - Naive vs. Optimized
AI 요약
Context
정렬된 두 배열을 하나의 배열로 병합하는 과정에서 단순 구현의 편의성과 실행 효율성 사이의 상충 관계 발생. 기존 Naive 방식은 고수준 API 활용으로 가독성은 높으나 정렬 비용으로 인한 성능 저하가 병목 지점으로 작용.
Technical Solution
- Splice 및 Sort API를 활용한 단순 병합 및 재정렬 방식의 Naive 설계
- 3개의 Pointer(i, j, k)를 도입한 역방향 순회 기반의 Optimized 설계
- nums1의 유효 데이터 끝점과 nums2의 끝점을 비교하여 가장 큰 값을 뒤에서부터 배치하는 구조
- While loop를 통한 단일 패스 순회로 추가적인 Sort 연산 제거
- nums1의 포인터가 먼저 소진될 경우를 대비한 nums2 잔여 데이터 복사 로직 구현
- In-place 수정을 통해 추가적인 메모리 할당을 방지한 공간 효율적 설계
실천 포인트
1. 고수준 내장 함수(Sort 등) 사용 시 내부 시간 복잡도를 검토했는가
2. 데이터가 이미 정렬된 상태라면 이를 활용해 O(n) 수준으로 최적화 가능한지 분석했는가
3. 추가 메모리 할당 없이 In-place 수정이 가능한 구조인지 확인했는가