[JS] Max Points on a Line

🔒 문제 (LeetCode 149)

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• All the points are unique.

 

🌊 입출력

Example 1:

Input: points = [[1,1],[2,2],[3,3]]
Output: 3

Example 2:

Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4

 

---

 

🔑 해결

🌌 알고리즘 - 완전탐색

두 점 사이의 기울기를 비교하여 같은 직선 상에 있는지 확인할 수 있다.

이 때 x좌표 값이 같으면 기울기가 무한대가 되고, y좌표 값이 같으면 기울기가 0이 되는 경우도 고려한다.

기울기를 key, 포함되는 점의 수를 value로 가지는 map을 만들고 최대 value 값을 찾으면 답이 된다.

/**
 * @param {number[][]} points
 * @return {number}
 */

var maxPoints = function(points) {
    const map = new Map();
    let result = 0;
    for(let i = 0; i < points.length; i ++) {
        
        const [p1x, p1y] = points[i];
        let max = 1;
        let slope;
        for(let j = i+1; j < points.length; j ++) {
            
            const [p2x, p2y] = points[j];
            
            if (p2x === p1x) // y = 무한대 일 경우
                slope = Number.MAX_SAFE_INTEGER;
            else 
                slope = (p2y - p1y)/(p2x - p1x);
            
            if(!map.has(slope))
                map.set(slope, 2);
            else
                map.set(slope, map.get(slope) + 1);
            
            max = Math.max(max, map.get(slope));
        }
        
        map.clear();
        result = Math.max(result, max);
        
    }
    return result;
};