[Java] LeetCode 149. Max Points on a Line

[Java] LeetCode 149. Max Points on a Line

 

문   제 : 

직교좌표계의 (x, y) 좌표를 나타내는 2차원 정수 배열 points가 주어진다. 

points의 점들이 모두 좌표계에 있다고 가정하고 

직선을 그었을 때 가장 많이 겹치는 점의 개수를 구해라.

• { 1 <= points.length <= 300 }
• { points[i].length == 2 }
• { -10^4 <= x, y <= 10^4 }

 

 

Example )

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

 

---

접   근 : 

점 두 개를 가지고 기울기를 구해 같은 기울기이면 직선상에 있는 점임을 이용해 기울에 따른 점의 개수를 구한다.

기울기와 점의 개수가 짝꿍으로 묶여있어야 하니 Hash Map을 사용

점 두 개를 가지고 기울기를 구해야 하니 반복문 2 중첩이 될 수 밖에 없는 구조일 것이다.

 

---

해   결 : 

점의 개수 만큼 반복문을 2중첩으로 돌린다.

 

HashMap을 처음부터 선언할 수 있지만 너무 커지면 메모리 낭비가 심해지니

max 변수를 선언 한 후 map은 일정 때마다 다시 재 선언해준다.

 

기울기를 key로, 그 기울기 위 점의 개수를 value로 가지는 HashMap 선언해준다.

 

기울기 구하는 공식 = (y값의 증가량) / (x값의 증가량)

 

기울기를 구한 후 map에 추가해준다. 

 

만약 이미 있는 기울기이면, 값을 +1해서 최신화 해주고, 없는 기울기이면 2로 초기화 해주면서 새로 추가해준다.

 

max를 최신화 해준다.

 

---

 

 

HashMap을 선언해준다.

 

Map<Double, Integer> map = new HashMap<>();

 

 

---

기울기 선이 세로로 일자일 경우 (기울기가 거의 무한대) 생략해준다.

 

if(i == j) continue; // 기울기 선이 세로로 일자일 경우

 

 

---

 

 

기울기를 구해주고 HashMap에 추가해준다. (새로운 기울기 값일 경우)

여기서 이미 있는 기울기 값이라면, 기존 값에 +1을 해준다.

그리고 max값을 최신화 해준다.

double slope = (points[i][1]-points[j][1])/(double)(points[i][0]-points[j][0]); // 기울기 구하기

map.put(slope, map.getOrDefault(slope, 1) + 1); // 기울기를 맵에 추가하는 과정

max = Math.max(max, map.get(slope)); // 최대 값 수정

 

---

결   과  :

class Solution {
    public int maxPoints(int[][] points) {
        int max=1;
        if(points.length == 1) return max;
        
        for(int i=0; i<points.length; i++){
            Map<Double, Integer> map = new HashMap<>();
            for(int j=0; j<points.length; j++){
                if(i == j) continue; // 기울기 선이 세로로 일자일 경우

                double slope = (points[i][1]-points[j][1])/(double)(points[i][0]-points[j][0]); // 기울기 구하기
                map.put(slope, map.getOrDefault(slope, 1) + 1); // 기울기를 맵에 추가하는 과정
                max = Math.max(max, map.get(slope)); // 최대 값 수정
            }
        }
        return max;
    }
}