Skip to main content

2040 - Kth Smallest Product of Two Sorted Arrays

info

풀이 키워드​

스포주의

이진탐색 투포인터


풀이 코드​

info
  • 메모리: 54840 KB
  • 시간: 211 ms
class Solution {
    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        /* 3 step solution */
        //    1. preprocess k with the total count of negative products
        //    2. start bsearch
        //    3. adjust search range via count of x which is leq than m

        List<Integer> anList = new ArrayList<>(); // a - negative
        List<Integer> apList = new ArrayList<>(); // a - positive
        List<Integer> bnList = new ArrayList<>(); // b - negative
        List<Integer> bpList = new ArrayList<>(); // b - positive

        separate(nums1, anList, apList);
        separate(nums2, bnList, bpList);

        long nProdCnt = (long)anList.size() * bpList.size() + (long)apList.size() * bnList.size();
        int sign = 1;
        List<Integer> a1 = anList;
        List<Integer> a2 = apList;
        List<Integer> b1, b2;

        if (k > nProdCnt) { // search pos
            k -= nProdCnt;
            b1 = bnList;
            b2 = bpList;
        }
        else { // search neg
            k = nProdCnt - k + 1;
            sign = -1;
            b1 = bpList;
            b2 = bnList;
        }

        // bsearch
        long l = 0, r = (long)1e10;
        while (l < r) {
            long m = (l + r) >> 1;
            if (cntLeqProd(a1, b1, m) + cntLeqProd(a2, b2, m) >= k) {
                r = m;
            }
            else {
                l = m + 1;
            }
        }

        return sign * l;
    }

    public void separate(int[] orig, List<Integer> neg, List<Integer> pos) {
        for (int n : orig) {
            if (n < 0) neg.add(-n); // abs
            else pos.add(n);
        }
        Collections.reverse(neg); // abs asc
    }

    public long cntLeqProd(List<Integer> a, List<Integer> b, long m) {
        long cnt = 0;
        int j = b.size() - 1; // reverse iteration (big -> small)

        // two-pointer optimization
        for (int n : a) {
            while (j > -1 && (long)n*b.get(j) > m) {
                --j; // need more smaller value
            }
            cnt += j + 1;
        }

        return cnt;
    }
}

풀이 해설​

문제 내용은 a * b 했을 때 오름차순으로 k번째 product 값을 구하라는 굉장히 심플한 요구사항이고

a, b 배열 모두 오름차순 정렬된 상태로 주기 때문에 친절한 것 같지만

실상은 조건 잘 나눠야 하는데다 성능 최적화까지 고려해야 하는 고난이도 문제이다.


🧐 두뇌를 풀가동해요​

WIP


메모​

  • 1번째 유형은 떠올랐는데 구현 방향을 못잡았고 2번째 유형은 생각 못했음
  • 여태 본 1번째 유형 문제 중 가장 구현이 복잡한듯
    • 음수 처리도 따로 해야 하는... semi 빡구현 수준
  • cntLeqProd 최적화 안하고 그냥 O(n2)O(n^2) 스캔하면 TLE 터짐