LeetCode 2040: 이진 탐색으로 K번째 작은 곱 찾기

LeetCode 2040: 두 정렬된 배열의 K번째 작은 곱 찾기

이 콘텐츠는 LeetCode의 고급 이진 탐색 문제를 소개하고, 두 개의 정렬된 배열에서 가능한 모든 곱(nums1[i] * nums2[j]) 중 K번째로 작은 값을 효율적으로 찾는 방법을 심층적으로 분석합니다.

핵심 기술

이 문제는 답 자체에 대한 이진 탐색(Binary Search on the Answer) 기법을 핵심으로 하며, 음수, 양수, 0을 포함하는 곱셈 연산의 특성을 고려하여 특정 값 x보다 작거나 같은 곱의 개수를 효율적으로 세는 countLE(x) 함수를 구현하는 것이 중요합니다.

기술적 세부사항

• 문제 정의: 두 개의 정렬된 정수 배열 nums1, nums2와 정수 k가 주어졌을 때, nums1[i] * nums2[j] 형태의 곱 중 K번째로 작은 값을 반환합니다.
• 브루트 포스 한계: 모든 곱을 생성하고 정렬하는 O(N*M)의 시간 복잡도는 배열 크기가 최대 5 * 10^4인 경우 비효율적입니다.
• 이진 탐색 전략: 가능한 곱의 값 범위(-1e10 ~ 1e10)에 대해 이진 탐색을 수행합니다.
  • countLE(x) 함수: 주어진 값 x 이하인 곱의 개수를 계산합니다.
    • nums1[i]가 음수일 경우: nums2에서 ceil(1.0 * x / nums1[i]) 보다 크거나 같은 첫 번째 원소를 찾기 위해 lower_bound 사용 (오름차순). 결과적으로 끝까지의 거리가 해당 개수가 됩니다.
    • nums1[i]가 양수일 경우: nums2에서 floor(1.0 * x / nums1[i]) 보다 작거나 같은 마지막 원소를 찾기 위해 upper_bound 사용 (오름차순). 결과적으로 처음부터의 거리가 해당 개수가 됩니다.
    • nums1[i]가 0일 경우: x가 0 이상이면 n2개의 곱이 x 이하가 됩니다.
• 탐색 범위: 곱의 값 범위는 -10^10에서 10^10까지 설정됩니다.
• 언어별 구현: C++, JavaScript, Python으로 각각의 countLE 함수 및 이진 탐색 로직이 제공됩니다.

개발 임팩트

• 탐색 공간 축소를 통한 시간 복잡도 개선: O(N*M)에서 O((N+M) * log(Range))로 효율화.
• 알고리즘 문제 해결 능력 향상: 이진 탐색의 다양한 응용 사례 학습.
• 엣지 케이스(음수, 0) 처리 능력 강화.

톤앤매너

개발자를 대상으로 하며, 문제 해결 과정을 명확하고 논리적으로 설명하는 전문적이고 교육적인 톤을 유지합니다.