[프로그래머스 2레벨] 교점에 별 만들기 (C++)

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;

vector<string> solution(vector<vector<int>> line) {
    set<pair<ll, ll>> points; //중복 없이 저장
    ll minX = 1e18, maxX = -1e18, minY = 1e18, maxY = -1e18;

    for (int i = 0; i < line.size(); i++) 
    {
        for (int j = i + 1; j < line.size(); j++) 
        {
            ll A = line[i][0], B = line[i][1], E = line[i][2];
            ll C = line[j][0], D = line[j][1], F = line[j][2];

            ll tmp = A * D - B * C; //분모
            if (tmp == 0) continue; // 평행 또는 일치

            ll x_numer = B * F - E * D; //분자
            ll y_numer = E * C - A * F;

            if (x_numer % tmp != 0 || y_numer % tmp != 0) continue; //정수 교점만 체크

            ll x = x_numer / tmp; //교점 좌표
            ll y = y_numer / tmp;
            points.insert({x, y});

            minX = min(minX, x);
            maxX = max(maxX, x);
            minY = min(minY, y);
            maxY = max(maxY, y);
        }
    }

    ll w = maxX - minX + 1;
    ll h = maxY - minY + 1;

    vector<string> answer(h, string(w, '.')); //.으로 채우기

    for (auto i : points) //해당 좌표만 * 처리 
    {
        ll r = maxY - i.second;     
        ll c = i.first - minX;
        answer[r][c] = '*';
    }

    return answer;
}

 

좌표를 중복 없이 저장하기 위해 set으로 저장한다.

이제 입력 값에 따라 값을 따로 분리하여 저장하고, 이를 통해 분모와 분자 값을 크래머의 공식을 따라 구해준다.

먼저 이렇게 구한 분모 값의 경우 0이되면 평행하거나 일치하다는 뜻이므로 스킵한다.

 

그리고 분자의 경우 정수 교점만 체크해야 하기 때문에 나머지가 0인지 체크해주어야 한다.

예를 들어 (2.1, -0.19) 이런 좌표는 정수 좌표가 아니기에 스킵해야 한다.

 

구한 분모, 분자 값을 통해 각 x, y를 구하고 이를 좌표 쌍으로 set에 저장한다.

그리고 그리드 총 길이를 구하기 위해 최대, 최소 x와 최대 최소 y 값을 구해준다.

그리고 해당 값들을 통해 w와 h의 값을 구하고, 기본 값인 .으로 채워 기본 그리드를 만들어준다.

 

이제 해당 좌표에 대해서만 * 처리를 해주어야한다.

여기서 주의할 점은 실제 좌표와 배열에서 *이 찍히는 위치가 다르다는 것이다.

예를 들어 예제의 (0, 4)는 (0, 1)이 될 것이다.

따라서 Y는 최대 Y 값에서 해당 Y 값을 빼주며 위치를 뒤집어 주어야 한다.

X 같은 경우는 최소 X 값을 길이에 맞게 0부터 시작하도록 보정해준다.