교점에 별 만들기 C++

https://school.programmers.co.kr/learn/courses/30/lessons/87377

프로그래머스

 

 

※ 문제

Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.

예를 들어, 다음과 같은 직선 5개를

• 2x - y + 4 = 0
• -2x - y + 4 = 0
• -y + 1 = 0
• 5x - 8y - 12 = 0
• 5x + 8y + 12 = 0

좌표 평면 위에 그리면 아래 그림과 같습니다.

이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)입니다.

만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.

위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다.

이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.

따라서 정답은

입니다.

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

 

 

 

 

※ 나의 풀이

식도 다 나와있어서 그렇게까지 어렵지는 않았다.

다만, 이 문제도 int의 범위를 넘어가는 변수가 있어서 long long을 이용해야 한다.

문제 풀기 전에 제약사항을 보자.

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<vector<int>> line) {
    vector<string> answer;
    
    // 정수 교차점 찾아주기
    long long max_x = -9223372036854775807, max_y = -9223372036854775807;
    long long min_x = 9223372036854775807, min_y = 9223372036854775807;
    vector<vector<long long>> cross_dots;
    for (int i = 0; i < line.size() - 1; i++)
    {
        for (int j = i + 1; j < line.size(); j++)
        {
            //vector<double> cross_dot = get_dot(
            //    line[i][0], line[i][1], line[i][2],
            //    line[j][0], line[j][1], line[j][2]
            //);
            long long A = line[i][0], B = line[i][1], E = line[i][2];
            long long C = line[j][0], D = line[j][1], F = line[j][2];

            vector<long long> cross_dot;
            long long cross_x = B * F - E * D;
            long long cross_y = E * C - A * F;
            long long mod = A * D - B * C;

            // 교차점이 없다면
            if (mod == 0) continue;
            // 정수가 아니면
            //if (!is_integer(cross_dot[0]) || !is_integer(cross_dot[1])) continue;
            if (cross_x % mod || cross_y % mod) continue;
            cross_dot.push_back(cross_x / mod);
            cross_dot.push_back(cross_y / mod);

            // x, y축 최소, 최대값 구해주기
            max_x = (max_x < cross_dot[0]) ? cross_dot[0] : max_x;
            min_x = (min_x > cross_dot[0]) ? cross_dot[0] : min_x;
            max_y = (max_y < cross_dot[1]) ? cross_dot[1] : max_y;
            min_y = (min_y > cross_dot[1]) ? cross_dot[1] : min_y;

            cross_dots.push_back(cross_dot);
        }
    }

    // cross_dots (0, 0) 기준으로 바꿔주기
    for (int i = 0; i < cross_dots.size(); i++)
    {
        cross_dots[i][0] -= min_x;
        cross_dots[i][1] -= min_y;
        //cross_dots[i][0] = cross_dots[i][0] + min_y;
        //cross_dots[i][1] = cross_dots[i][1] - min_x;
    }
    max_x -= min_x;
    min_x -= min_x;
    max_y -= min_y;
    min_y -= min_y;

    // answer 만들어주기
    string tmp;
    for (int i = 0; i <= max_x; i++)
    {
        tmp += ".";
    }
    for (int i = 0; i <= max_y; i++)
    {
        answer.push_back(tmp);
    }

    for (int i = 0; i < cross_dots.size(); i++)
    {
        long long x = cross_dots[i][1];
        long long y = cross_dots[i][0];
        answer[x][y] = '*';
    }

    reverse(answer.begin(), answer.end());
    
    return answer;
}