합배송 가능한 상품 쌍

문제

한 오픈마켓은 서로 다른 상품 두 개를 하나의 박스에 담아 보내는 합배송 요금제를 운영합니다. 이 요금제는 두 상품의 무게 합이 lo 이상 hi 이하인 경우에만 적용됩니다. 합이 lo 미만이면 최소 요금 구간에 못 미쳐 개별 배송이 더 싸고, hi를 넘으면 박스 하중을 초과합니다.

상품들의 무게가 담긴 정수 배열 weights와 두 정수 lo, hi가 주어질 때, 합배송이 가능한 상품 쌍의 개수 를 반환하는 solution(weights, lo, hi) 함수를 완성하세요.

• 쌍은 서로 다른 두 위치 의 상품을 고르는 것입니다. 즉 (i, j)에서 i < j인 조합을 셉니다.
• 무게가 같은 상품이 여러 개 있으면 각각 다른 상품으로 취급합니다.
• "몇 쌍을 만들 수 있는지" 가능한 조합의 수를 세는 문제이며, 한 상품이 여러 쌍에 중복으로 등장해도 괜찮습니다. (실제로 배송을 확정하는 것은 아닙니다.)

예시

제약 조건

• 1 ≤ weights.length ≤ 100,000
• 1 ≤ weights[i] ≤ 1,000,000,000
• 0 ≤ lo ≤ hi ≤ 2,000,000,000
• lo, hi는 정수입니다.
• 상품이 1개뿐이면 만들 수 있는 쌍이 없으므로 0을 반환합니다.
• 반환값은 최대 약 50억까지 커질 수 있으나 JavaScript의 number로 정확히 표현 가능한 범위입니다.
• 모든 쌍을 하나씩 확인하는 O(N²) 풀이는 시간 초과됩니다.

시간 복잡도 목표: O(N log N)

공간 복잡도 목표: O(N) 이하 (정렬 공간 제외 시 O(1))