[LeetCode] 149. Max Points on a Line

😎풀이

해당 문제는 점의 기울기를 구하는 공식을 알면 풀이가 간단한 문제이다.

두 점의 기울기를 구하는 방법은 다음과 같다.

기울기 = y2 − y1 / x2 − x1

해당 공식을 바탕으로 2중 반복하며 각 좌표별 최대 위치할 수 있는 같은 기울기의 점 수를 구하면 된다.

function maxPoints(points: number[][]): number {
    // 2개 이하의 점이 있을 경우 모두 연결 가능
    if(points.length <= 2) return points.length
    let countMaxPoint = Number.MIN_SAFE_INTEGER

    for(let i = 0; i < points.length; i++) {
        const [y1, x1] = points[i]
        // key: 기울기, value: 해당 기울기의 점 수
        const tiltMap = new Map<number, number>()
        for(let j = 0; j < points.length; j++) {
            // 같은 점 계산 안 함
            if(i === j) continue
            const [y2, x2] = points[j]
            // 두 좌표의 차이 계산
            const dy = y1 - y2
            const dx = x1 - x2
            // 최대 공약수 계산
            const gcd = getGCD(Math.abs(dy), Math.abs(dx))
            // 정수 범위를 벗어나지 않기 위해 최대 공약수로 나눔
            const curKey = (dy / gcd) / (dx / gcd)
            const curValue = (tiltMap.get(curKey) ?? 1) + 1
            // 현재 key + 1
            tiltMap.set(curKey, curValue)
            // 최댓값 갱신
            countMaxPoint = Math.max(countMaxPoint, curValue)
        }
    }

    return countMaxPoint
};
// 최대 공약수
function getGCD(a: number, b: number) {
    return b === 0 ? a : getGCD(b, a % b)
}