Kth 최소 곱 찾기 - LeetCode 2040 문제 분석 및 해결 전략

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

알고리즘, 데이터 구조, 이진 탐색

대상자

- 알고리즘 문제 풀이에 관심 있는 개발자

- 이진 탐색과 복잡한 조건 처리에 대한 이해가 필요한 중급 이상 개발자

- 음수, 0, 양수의 곱에 대한 경우 분석이 필요한 문제 해결자

핵심 요약

• 이진 탐색을 제품 공간에 적용하여 kth 최소 곱을 효율적으로 찾는 방법
• countLE(x) 함수를 통해 제품이 x 이하인 경우의 수를 계산하여 이진 탐색 범위를 조정
• 음수, 0, 양수에 따른 분기 처리가 핵심 (예: nums1[i] < 0, nums1[i] > 0, nums1[i] == 0)

섹션별 세부 요약

1. 문제 정의 및 제약 조건

• 두 정렬된 배열 nums1, nums2와 정수 k가 주어짐
• 모든 가능한 곱 nums1[i] * nums2[j] 중 kth 최소 값을 반환해야 함
• 배열 크기 최대 5 10^4 → O(NM) 시간 복잡도는 불가능
• 부호(음수, 0, 양수)와 곱의 범위가 핵심 고려 요소

2. 브루트 포스 접근법의 한계

• 모든 곱 계산 후 정렬 → 시간 복잡도 O(NM log(NM))
• N, M = 5e4 시 2.5e9 연산 → 실용 불가능

3. 이진 탐색 적용 전략

• 이진 탐색의 대상: 곱의 값 (x)
• 탐색 범위: -1e10 ~ 1e10
• countLE(x) 함수를 통해 x 이하인 곱의 수를 계산하여 k 이상인지 확인

4. countLE(x) 함수 구현

• nums1[i] < 0 → nums2[j] >= ceil(x / nums1[i])
• nums1[i] > 0 → nums2[j] <= floor(x / nums1[i])
• nums1[i] == 0 → x >= 0 시 n2 개의 곱 존재
• 이진 탐색을 통해 nums2에서 조건에 맞는 요소 수 계산

5. 언어별 구현 예시

• C++: lower_bound, upper_bound 사용
• JavaScript: 이진 탐색을 직접 구현 (lo, hi 조정)
• Python: bisect_left, bisect_right 활용

결론

• 이진 탐색을 통해 O(log(1e20)) 시간 복잡도로 문제 해결 가능
• 부호에 따른 분기 처리가 필수 (음수, 0, 양수)
• countLE(x) 함수의 정확한 구현이 성능 향상에 직접적으로 영향
• 언어별 구현 시 bisect 모듈 또는 이진 탐색 직접 구현 활용 권장