프로그래머스 - 교점에 별 만들기 [C++]

이 문제는 수학, map을 이용해서 풀었다.

 

최대 1,000개의 line 중 2개를 선택하므로 10C2 = 499,500 번의 연산으로 짝을 지어줄 수 있다.

 

각 짝에 대해서 Ax + By + E = 0, Cx + Dy + F = 0 에 대한 교점 수식이 주어진다. 여기서 핵심은 어떻게 정수가 아닌 소수인지를 판단하는 것인데, 나는 나누어떨어지지 않으면 소수라고 판정하는 방식으로 구현했다.

 

calculate() 는 연산만 수행하므로 O(1) 이기 때문에 시간 안에 풀 수 있다. 그러나 주의할 점은 NO_MEET로 놓은 숫자가 생각보다 많이 커야 한다는 것이다. 1e15 정도로 커야 문제가 풀리게 된다. 또한 int 자료형으로는 100,000 * 100,000 = 100억의 숫자를 담을 수 없으므로 long long을 사용해야 한다. 

#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;

#define NO_MEET 100000000000000ll
typedef long long LL;

map<pair<LL, LL>, bool> stars;

pair<LL, LL> calculate(vector<int>& abe, vector<int>& cdf)
{
    LL a = abe[0];
    LL b = abe[1];
    LL e = abe[2];
    LL c = cdf[0];
    LL d = cdf[1];
    LL f = cdf[2];
    
    LL ad_bc = a*d - b*c;
    if (ad_bc == 0)
    {
        return {NO_MEET, NO_MEET};
    }
    
    LL bf_ed = b*f - e*d;
    LL ec_af = e*c - a*f;
    if (bf_ed % ad_bc != 0 || ec_af % ad_bc != 0)
    {
        return {NO_MEET, NO_MEET};
    }
    
    LL y = ec_af / ad_bc;
    LL x = bf_ed / ad_bc;
    return {y, x};
}

vector<string> solution(vector<vector<int>> line) 
{
    LL up = -NO_MEET;
    LL down = NO_MEET;
    LL left = NO_MEET;
    LL right = -NO_MEET;
    
    LL allSize = line.size();
    for (int i = 0; i < allSize; i++)
    {
        for (int j = i + 1; j < allSize; j++)
        {
            vector<int> abe = line[i];
            vector<int> cdf = line[j];
            pair<LL, LL> result = calculate(abe, cdf);
            if (result.first == NO_MEET && result.second == NO_MEET)
            {
                continue;
            }
            
            LL y = result.first;
            LL x = result.second;
            up = max(up, y);
            down = min(down, y);
            left = min(left, x);
            right = max(right, x);
            stars[result] = true;
        }
    }
    
    vector<string> answer;
    for (LL y = up; y >= down; y--)
    {
        string temp = "";
        for (LL x = left; x <= right; x++)
        {
            if (stars[{y, x}])
            {
                temp += '*';
            }
            else
            {
                temp += '.';
            }
        }
        answer.push_back(temp);
    }
    return answer;
}