Level 0. 평행

Level 0. 평행

 

 

두 선분이 평행하다는 것은 기울기가 같다는 뜻이다.

 

2중 for문을 이용해 조합을 만들고 vector에 기울기를 저장하여 매번 비교하는 식으로 해결했다.

 

하지만, 2중 for문 안에 find 함수가 있기 때문에 사실상 O(n³)의 복잡도를 갖는다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> dots)
{
    vector<float> slopes;

    for (auto it = dots.begin(); it < dots.end() - 1; ++it)
    {
        for (auto jt = it + 1; jt < dots.end(); ++jt)
        {
            float x1 = (*it)[0], y1 = (*it)[1];
            float x2 = (*jt)[0], y2 = (*jt)[1];
            float slope = (y2 - y1) / (x2 - x1);

            if (find(slopes.begin(), slopes.end(), slope) != slopes.end())
                return 1;
            else
                slopes.emplace_back(slope);
        }
    }

    return 0;
}

 

vector 대신 unordered_set을 이용해 좀 더 개선해보았다.

 

set이 아닌 unordered_set을 사용한 이유는 정렬된 상태를 유지할 필요가 없고 레드-블랙 트리 대신 해시 테이블을 사용하기 때문에 삽입에 O(1) 시간이 걸리기 때문이다.

 

2중 for문 조합 안에서는 기울기를 삽입만 하고 unordered_set의 중복 불허 특성을 이용해 마지막에 조합과 unordered_set의 크기를 비교하여 해결했다.

 

값 대신 크기를 비교하게 하면서 O(n³)의 복잡도를 O(n²)으로 줄였다.

 

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int solution(vector<vector<int>> dots)
{
    unordered_set<float> grad;
    int occur = dots.size() * (dots.size() - 1) / 2;

    for (auto it = dots.begin(); it < dots.end() - 1; ++it)
    {
        for (auto jt = it + 1; jt < dots.end(); ++jt)
        {
            float x1 = (*it)[0], y1 = (*it)[1];
            float x2 = (*jt)[0], y2 = (*jt)[1];

            grad.emplace((y2 - y1) / (x2 - x1));
        }
    }

    return grad.size() != occur;
}