[Leetcode] 3623. Count Number of Trapezoids I

점들의 배열 points 가 주어지고 이 점들을 이어 만들 수 있는 사다리꼴의 최대 갯수를 구하는 문제. 사다리꼴이란 마주보는 두 변이 평행한 사각형 이다. 지문에서 "수평 사다리꼴" 이라고 범위를 좁혀주기에 y 축이 같은 점들이 그 대상이 된다고 보면 된다.

y축이 같은 점들을 모아 콤비네이션을 구하고, 각 수평선 마다 하나씩 고르면 되므로 구간합을 적용해주면 된다. 구간합을 안하고 그냥 이중 포문을 돌리면 시간초과(...) 가 뜬다.

이 문제는 특이하게도 모든 원소의 최댓값이 10^9 라서 원소끼리의 곱셈을 하는 순간 오버플로우가 발생할 수 있다. 최대 크기가 9*10^15 인 Number 타입을 가지고는 문제를 풀 수가 없다. BigInt 타입을 사용하면 메모리가 허용하는 한 무한한 숫자를 표현할 수 있기에 사용해보았다. BigInt는 숫자 뒤에 n 을 붙이거나 new BigInt() 생성자를 이용해 만들 수 있다.

const MODULO = BigInt(Math.pow(10, 9) + 7);

function countTrapezoids(points: number[][]): number {
    const pointMap = new Map()

    for (const [_, y] of points) {
        pointMap.set(y, (pointMap.get(y) || 0) + 1);
    }

    let sum = 0n;
    let innerSum = 0n;

    for (const count of pointMap.values()) {
        if (count < 2) {
            continue;
        }

        const n = BigInt(count);
        const currentComb = n * (n - 1n) / 2n;
        sum = (sum + innerSum * currentComb) % MODULO;
        innerSum = (innerSum + currentComb) % MODULO;
    }

    return Number(sum);
};

function combinations(n: number, r: number) {
    if (n < r) {
        return 0;
    }

    if (r === 2) {
        return (n * (n - 1)) / 2;
    }

    let result = 1;
    for (let i = 0; i < r; i++) {
        result = result * (n - i) / (i + 1);
    }

    return Math.round(result);
}