[프로그래머스][C++] 평행

평행

문제 링크

평행

분석

주어진 네 점이 이루는 선분 중 두 선분이 평행한지 여부를 판별하는 문제입니다.

두 점을 잇는 직선의 기울기를 구하여 값이 같은지 확인해주면 됩니다.
값이 같을 경우 평행하다는 것을 의미하기 때문입니다.

기울기를 구하는 공식은 다음과 같습니다.

$slope = \frac {y값의 증가량}{x값의 증가량} = \frac {y2 - y1}{x2 - x1} = \frac {y1 - y2}{x1 - x2}$

풀이

#include <vector>
#include <cmath>

using namespace std;

// 두 선분이 평행한지 판별하는 함수
bool isparallel(vector<int> p1, vector<int>p2, vector<int>p3, vector<int>p4)
{    
    return (double)(p2[1] - p1[1]) / (p2[0] - p1[0]) == 
        (double)(p4[1] - p3[1]) / (p4[0] - p3[0]);
}

int solution(vector<vector<int>> dots) {
    int answer = 0;
    
    // 점 4개를 두 쌍으로 나눈 다면, 경우의 수는 3가지뿐
    // (0, 1) (2, 3)
    // (0, 2) (3, 1)
    // (0, 3) (1, 2)
    if (isparallel(dots[0], dots[1], dots[2], dots[3]) ||
       isparallel(dots[0], dots[2], dots[3], dots[1]) ||
       isparallel(dots[0], dots[3], dots[1], dots[2]))
    {
        // 평행한 선분이 존재하는 경우 값 변경
        answer = 1;
    }
    
    return answer;
}

경우의 수에서 두 쌍을 구할 때, 점 순서는 결과에 영향이 없기 때문에 3가지입니다.

성능 요약

시간 복잡도는 상수 시간에 끝나기 때문에 $O(1)$입니다.

• 점 4개가 두 쌍으로 나뉘는 경우의 수 $O(3) \approx O(1)$

공간 복잡도는 추가적인 공간을 사용하지 않기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.11MB)
테스트 2 〉 통과 (0.01ms, 4.19MB)
테스트 3 〉 통과 (0.01ms, 4.12MB)
테스트 4 〉 통과 (0.01ms, 4.21MB)
테스트 5 〉 통과 (0.01ms, 4.17MB)
테스트 6 〉 통과 (0.01ms, 3.67MB)
테스트 7 〉 통과 (0.01ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.17MB)
테스트 9 〉 통과 (0.01ms, 3.74MB)
테스트 10 〉 통과 (0.01ms, 4.13MB)
테스트 11 〉 통과 (0.01ms, 4.18MB)
테스트 12 〉 통과 (0.01ms, 3.86MB)
테스트 13 〉 통과 (0.01ms, 4.17MB)
테스트 14 〉 통과 (0.01ms, 4.19MB)
테스트 15 〉 통과 (0.01ms, 4.13MB)
테스트 16 〉 통과 (0.01ms, 4.19MB)
테스트 17 〉 통과 (0.01ms, 4.19MB)