<Hard> Max Points on a Line (LeetCode : C#)

https://leetcode.com/problems/max-points-on-a-line/

📕 문제 설명

2차원 좌표들이 주어질 때 한 직선에 존재 가능한 가장 많은 점의 개수 반환하기

• Input
  2차원 좌표들 (int[][])
• Output
  한 직선에 존재 가능한 가장 많은 점의 개수 (int)

예제

풀이

모든 지점 별 가능한 slope들 구해서 해당 position 기준 최대와 전체 최대를 비교해서 갱신하는 방식 (brute-force, O(N^2))

public class Solution {
    public int MaxPoints(int[][] points) {
        if (points.Length == 1) return 1;
        Dictionary<double, int> countDict = new Dictionary<double, int>();
        int maxPoints = 0;
        for (int i = 0; i < points.Length; i++)
        {
            countDict.Clear();
            for (int j = 0; j < points.Length; j++)
            {
                if (i == j) continue;

                int x1 = points[i][0];
                int x2 = points[j][0];

                int y1 = points[i][1];
                int y2 = points[j][1];

                double slope = (double) (y2 - y1) / (x2 - x1);

                if (countDict.TryGetValue(slope, out int count))
                {
                    countDict[slope] += 1;
                }
                else
                {
                    countDict.Add(slope, 2);
                }
            }

            maxPoints = Math.Max(maxPoints, countDict.Values.ToList().Max());
        }

        return maxPoints;
    }
}

결과