[Programmers] #120875 - 평행 [Java][C++][Python]

문제 링크

---

1. 아이디어

네 점의 좌표가 담긴 dots를 두 점씩 묶어 만든 두 직선 중 평행한 경우가 하나라도 있으면 1을, 없으면 0을 반환하는 문제로 네 점을 두 쌍으로 나누는 경우의 수 3가지를 전부 확인하면서 각 경우 두 직선이 평행한지 판별하면 된다.

평행 여부는 기울기를 구해 비교하면 되지만 실수 나눗셈이라 정밀도 오차가 생길 수 있다. 점 $(x_1, y_1)$, $(x_2, y_2)$을 지나는 직선의 기울기 $\dfrac{y_1 - y_2}{x_1 - x_2}$와 점 $(x_3, y_3)$, $(x_4, y_4)$을 지나는 직선의 기울기 $\dfrac{y_3 - y_4}{x_3 - x_4}$가 같은지를, 양변에 분모를 곱해 나눗셈 없이 $(y_1 - y_2)(x_3 - x_4) = (y_3 - y_4)(x_1 - x_2)$인지로 판별했다. 두 직선이 겹치는 경우도 이 등식이 성립하므로 별도 분기 없이 평행으로 자동 포함된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(1)$	$O(1)$

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int[][] dots) {
        int[] p1 = dots[0], p2 = dots[1], p3 = dots[2], p4 = dots[3];
        return isParallel(p1, p2, p3, p4) || isParallel(p1, p3, p2, p4) || isParallel(p1, p4, p2, p3) ? 1 : 0;
    }

    static boolean isParallel(int[] p1, int[] p2, int[] p3, int[] p4) {
        return (p1[0] - p2[0]) * (p3[1] - p4[1]) == (p3[0] - p4[0]) * (p1[1] - p2[1]);
    }
}

#include <bits/stdc++.h>
using namespace std;

bool is_parallel(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
    return (p1[0] - p2[0]) * (p3[1] - p4[1]) == (p3[0] - p4[0]) * (p1[1] - p2[1]);
}

int solution(vector<vector<int>> dots) {
    vector<int> p1 = dots[0], p2 = dots[1], p3 = dots[2], p4 = dots[3];
    return is_parallel(p1, p2, p3, p4) || is_parallel(p1, p3, p2, p4) || is_parallel(p1, p4, p2, p3);
}

def is_parallel(p1, p2, p3, p4):
    return (p1[0] - p2[0]) * (p3[1] - p4[1]) == (p3[0] - p4[0]) * (p1[1] - p2[1])


def solution(dots):
    p1, p2, p3, p4 = dots
    return int(is_parallel(p1, p2, p3, p4) or is_parallel(p1, p3, p2, p4) or is_parallel(p1, p4, p2, p3))

---