Daily LeetCode Challenge - 149. Max Points on a Line

Problem From.

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

오늘 문제는 points 배열에 점들이 주어졌을때, 한 선분 위에 겹치는 점들 중 최대값을 반환하는 문제였다.

겹치는 점들의 갯수를 구하기 위해 slope 를 구했고, slope 를 map 의 key 값으로 하여 value 에 겹치는 점들의 갯수를 넣었다.

points 배열을 순회하며 처음에 한점을 잡고, 그 점을 기준으로 다른 점들과의 기울기를 구하여 기울기가 같으면 value 에 1을 추가하는 식으로 하였다.

여기서 주의해야할 점은 각 점을 선택할 때마다 map 을 초기화 시켜주어서 기울기들을 새로 구해주어야 한다는 점이었다. 마지막에는 선택된 점의 갯수도 넣어야하기 때문에 +1 을 해주었다.

class Solution {
    fun maxPoints(points: Array<IntArray>): Int {
        var max = 0
        
        for(i in 0 until points.size) {
            
            val map = hashMapOf<Double, Int>()
            
            for(j in 0 until points.size) {
                
                if(points[i] == points[j]) continue
                
                val slope = (points[j][0] - points[i][0]) / (points[j][1] - points[i][1]).toDouble()
                map.put(slope , map.getOrDefault(slope, 0) + 1)   
                max = Math.max(max, map.getOrDefault(slope, 0))
                
            }
        }
        return max + 1  
    }
}

위 문제의 시간복잡도는 O(n^2) 가 된다.