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

문제 설명

Ax + By + C = 0 형태로 되어 있는 n개의 직선이 (A, B, C) 로 2차원 벡터로 데이터를 제공한다.

n개의 직선들의 교점 중 정수로만 이루어진 교점을 찾고,

교점에는 "*" 별 모양으로 표시하고 나머지 좌표는 "."으로 채운다.

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

 

※참고 사항

Ax + By + E = 0

Cx + Dy + F = 0

두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

또, AD - EC = 0 인 경우 두 직선은 평행 또는 일치합니다.

제한 사항

• line의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다.
  • line의 가로(열) 길이는 3입니다.
  • line의 각 원소는 [A, B, C] 형태입니다.
  • A, B, C는 -100,000 이상 100,000 이하인 정수입니다.
  • 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
  • A = 0이면서 B = 0인 경우는 주어지지 않습니다.
• 정답은 1,000 * 1,000 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

입출력 예

line	result
[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]	["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]
[[0, 1, -1], [1, 0, -1], [1, 0, 1]]	["*.*"]
[[1, -1, 0], [2, -1, 0]]	["*"]
[[1, -1, 0], [2, -1, 0], [4, -1, 0]]	["*"]

풀이

문제에서 교점을 찾기 위해 필요한 수식이 주어졌다.

식을 사용해서 교점을 찾아야 한다.

 

1. 직선 2개씩을 비교하여 교점 계산을 한다.(위 식을 사용해서 교점 계산)

2. "AD - BC = 0" 가 나온다면,  평행 또는 일치하는 경우이므로 두 직선은 교점이 없다. 다음 직선과 비교를 진행한다.

3.  (BF - ED) % (AD - EC) 나머지가 0이 아닐 경우, 정수가 아니므로 다음 직선과 비교를 진행한다.

     (EC - AF) % (AD - EC) 도 동일하게 검사한다.

4. 교점 x, y를 구하고 벡터에 저장한다.

5. x , y의 최소값과 최댓값을 저장한다. (격자판에 나타내기 위한 최소한의 크기를 위해)

6. 격자판의 크기를 계산한다. (x는 행, y는 열)

    행 크기는  " x최댓값 - x최소값 + 1 " 이다. (0포함하기 위해 +1한다.)

    열 크기는 " y최댓값 - y최소값 + 1 "

7. 정확한 좌표 값을 찾는 문제가 아니다.

    ".", "*" 문자로 거리를 표현하기만 하면 된다.

    x는 작은 값, y는 큰 값 부터 적용되어야 한다.

    print는 파란색 동그라미 부터 시작되니까!! 

   (이 부분이 이해가 안갔는데 계속 고민하다가 떠올랐다. 후,,,)    

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

using namespace std;

vector<string> solution(vector<vector<int>> line) {
    
    long long minX = LLONG_MAX, minY = LLONG_MAX;
    long long maxX = LLONG_MIN, maxY = LLONG_MIN;
    
    vector<pair<long long, long long>> coords;
    int lineSize = line.size();
    for(int i = 0; i < lineSize; i++){
        for(int j = i + 1; j < lineSize; j++){
            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];
            
            long long xNumberator = B * F * 1LL - E * D * 1LL;
            long long yNumberator = E * C * 1LL - A * F * 1LL;
            
            long long mod = A * D * 1LL - B * C * 1LL;
            
            if(mod == 0){
                continue;
            }
            
            if(xNumberator % mod || yNumberator % mod){
                continue;
            }
            
            long long x = xNumberator / mod;
            long long y = yNumberator / mod;
            
            minX = min(minX, x);
            minY = min(minY, y);
            
            maxX = max(maxX, x);
            maxY = max(maxY, y);
            
            coords.push_back({x, y});
            
        }
    }
    
    string row = string(maxX - minX + 1, '.');
    vector<string> answer(maxY - minY + 1, row);
    
    for(auto &it : coords){
        answer[abs(it.second - maxY)][abs( it.first - minX)] = '*';
    }
    
    return answer;
}