[프로그래머스] (Java) 평행

 

 

📑 1. 문제설명

---

💡 2. 풀이과정

기울기 구하는 공식

두 직선이 평행하려면 기울기(slope) 가 같아야 한다.

두 점 (x1, y1), (x2, y2)의 기울기를 구하는 공식은 아래와 같다. 

이것을 코드로 쓰면 아래와 같다.

(double)(p2[1] - p1[1]) / (p2[0] - p1[0]);

처음에 나는 기울기를 구할 때 오름차순 정렬을 해서 큰 수에서 작은 수를 빼야 한다고 생각했는데

이 코드에서 배열을 정렬할 필요가 없다고 한다.  어떤 점을 먼저 쓰든 결과는 똑같기 때문이다. 
왜냐하면 두 점의 순서를 바꾸면 분자와 분모가 모두 부호가 반대가 되기 때문이다. 

점 4개로 만들 수 있는 평행한 선분쌍의 개수

 

처음에는 점 4개로 만들 수 있는 겹치지 않는 선분 쌍은 위 2쌍이라고 생각했는데 3쌍이 된다.

예를 들면 배열 dots가 문제에서 제시된 [[3, 5], [4, 1], [2, 4], [5, 10]] 라면 이 네 개의 점으로 만들 수 있는 서로 겹치지 않는 두 선분 쌍 3가지는 아래와 같다. 

 

[0,1] vs [2,3]
선분 1: (3,5) — (4,1)
선분 2: (2,4) — (5,10)

[0,2] vs [1,3]
선분 1: (3,5) — (2,4)
선분 2: (4,1) — (5,10)

[0,3] vs [1,2]
선분 1: (3,5) — (5,10)
선분 2: (4,1) — (2,4)

 

이렇게 나처럼 그려보지 않고 구하는 법은 조합 공식을 쓰는 것이다. 

C(4,2) = 6가지이다.

그런데 이 중 같은 두 쌍의 구성만 바꾼 경우는 중복이다.

예를 들어 (A,B)와 (C,D)  (C,D)와 (A,B) 는 사실 같은 조합이다. 
따라서 중복을 제거한 4개의 점으로 만들 수 있는 두 점씩 이은 6개의 선분 중,
서로 겹치지 않는 (즉, 점이 겹치지 않는) 두 선분 조합은 6/2=3으로 3쌍이다.

(0,1) vs (2,3)
(0,2) vs (1,3)
(0,3) vs (1,2)

각 경우의 기울기를 비교해서 같은 게 있다면 → 1
모두 다르면 → 0

 

기울기는 정수 비교 하는 것이 좋다.

기울기 비교할 때 나눗셈은 위험하다. x2 - x1 또는 x4 - x3가 0이면 0으로 나누기 예외가 발생하기 때문이다. 
그리고 실수 계산 (double)은 정밀도 오차가 날 수 있다. 그래서 기울기가 같다는 조건만 유지하면서 곱셈 비교를 하는 것이다.

아래의 식은 기울기를 직접 나누지 않고, 대신 정수 곱셈으로 비교하는 방식이다.

(y2 - y1) * (x4 - x3) == (y4 - y3) * (x2 - x1)

 

어떻게 이 식이 나왔는지에 관해서 두 직선의 기울기가 같다는 건 아래의 수식으로 표현할 수 있다. 

양변에 `x_2 - x_1`와 `x_4 - x_3`를 곱해버리면 이렇게 된다.

이렇게 하면 분모가 0인 상황을 방지 가능하고 정수끼리 계산해서 오차가 없으며 성능도 더 좋다.

---

👨‍💻 3. 정답코드

class Solution {
    // 기울기 계산 함수
    double slope(int[] p1, int[] p2) {
        return (double)(p2[1]-p1[1]) / (p2[0]-p1[0]);
    }
    public int solution(int[][] dots) {
        // 각 조합별 기울기 비교
        if (slope(dots[0], dots[1]) == slope(dots[2], dots[3])) return 1; 
        if (slope(dots[0], dots[2]) == slope(dots[1], dots[3])) return 1; 
        if (slope(dots[0], dots[3]) == slope(dots[1], dots[2])) return 1; 
        return 0;
    }
}

---

👏🏻 4. 좋아요 가장 많이 받은 코드

class Solution {
    int[][] dots;

    public int solution(int[][] dots) {
        this.dots = dots;
        if (parallel(0, 1, 2, 3)) return 1;
        if (parallel(0, 2, 1, 3)) return 1;
        if (parallel(0, 3, 1, 2)) return 1;
        return 0;
    }

    boolean parallel(int a, int b, int c, int d) {
        int x = (dots[a][0] - dots[b][0]) * (dots[c][1] - dots[d][1]);
        int y = (dots[a][1] - dots[b][1]) * (dots[c][0] - dots[d][0]);
        return x == y || x == -y;
    }
}

마지막에는 기울기 방향까지 고려해서 기울기가 반대인 경우도 고려해서 리턴...