[programmers] 교점에 별 만들기

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

math

 

---------------------------------------------------풀이----------------------------------------------------

 

문제 아래쪽에 나온 공식을 그대로 풀면 된다.

Ax + By + E = 0
Cx + Dy + F = 0
x = (BF-ED)/(AD-BC), y = (EC-AF)/(AD-BC)
(AD-BC == 0 이면 두 직선은 평행 또는 일치)

line에서 i와 j 2개씩을 선택해서(i는 0부터 n까지, j는 i+1부터 n까지)

분모인 AD-BC를 구하고, 이 값이 0이면 패스한다.

아니면 위 공식에 따라 x와 y를 구하고 그 값이 정수이면 set에 추가한다.

set에 추가된 값들 중에서 x와 y의 최소 최대 범위를 구하고,

그 범위를 돌면서 해당 정수 좌표 값이 set에 존재하면 *을 출력, 아니면 .을 출력한다.

#include <string>
#include <vector>
#include <set>
#include <cstdio>
#include <iostream>
#include <limits.h>

using namespace std;

vector<string> solution(vector<vector<int>> line) {
    vector<string> answer;
    set<pair<long long,long long> > s;   // 교집합 쌍들
    // Ax + By + E = 0
    // Cx + Dy + F = 0
    // x = (BF-ED)/(AD-BC), y = (EC-AF)/(AD-BC)
    // AD-BC == 0 이면 두 직선은 평행 또는 일치
    for(int i = 0; i < line.size(); i++){
        for(int j = i+1; j < line.size(); j++){
            // 분모 AD-BC
            long long denominator = (long long)line[i][0]*line[j][1] - (long long)line[i][1]*line[j][0];
            if(denominator == 0){
                continue;
            }
            double x = (double)((long long)line[i][1]*line[j][2] - (long long)line[i][2]*line[j][1]) / denominator;
            double y = (double)((long long)line[i][2]*line[j][0] - (long long)line[i][0]*line[j][2]) / denominator;
            // 둘 다 정수이면 set에 저장
            if(x == (long long)x && y == (long long)y){
                s.insert(make_pair((long long)x, (long long)y));
            }
        }
    }
    long long min_x = LLONG_MAX, min_y = LLONG_MAX, max_x = LLONG_MIN, max_y = LLONG_MIN;
    for(auto it = s.begin(); it != s.end(); it++){
        if(min_x > it->first){
            min_x = it->first;
        }
        if(max_x < it->first){
            max_x = it->first;
        }
        if(min_y > it->second){
            min_y = it->second;
        }
        if(max_y < it->second){
            max_y = it->second;
        }
    }
    for(long long j = max_y; j >= min_y; j--){
        string str = "";
        for(long long i = min_x; i <= max_x; i++){
            if(s.find({i,j}) != s.end()){
                str += "*";
            }
            else{
                str += ".";
            }
        }
        answer.push_back(str);
    }
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

이 문제에서의 핵심은

공식을 찾아내는 것과 type casting을 제대로 하는 것이 아니었을까 싶다.

공식은 사실, 문제 아래에 나와있어서 간단하지만, 이걸 못 보고 풀기 시작했을 때에는

저런 곱셈 형태로 공식을 만들지 않고, 나눗셈이 엄청 들어간 형태로 만들어서 온갖 예외처리가 필요했었다.

즉, Ax+By+C=0과 ax+by+c=0에서

y = -(A/B)x-(C/B) = -(a/b)x-(c/b)이고,

x = (c/b-C/B) / (A/B-a/b) 라는 식이 나온다.

여기서 예외처리는 b가 0일 경우, B가 0일 경우, A/B-a/b가 0일 경우를 모두 따로 해줘야하기 때문에 복잡하다.

따라서, 이 식을 곱하기 형태로 고친

x = (cB-Cb) / (Ab-aB)라는 식이 문제 아래에 제공된다. (이걸 빨리 봤으면 2시간은 절약했을 것 같지만, 그래도 이런 발상이 존재한다는 것을 배운 것에 의미를...)

 

다음은 type casting 문제이다.

double x = (double)(line[i][1]*line[j][2] - line[i][2]*line[j][1]) / denominator;
double y = (double)(line[i][2]*line[j][0] - line[i][0]*line[j][2]) / denominator;

여기서 분자를 계산하는 부분에 type casting이 쓰인다.

x = (BF-ED)/(AD-BC), y = (EC-AF)/(AD-BC)에서

BF-ED와 EC-AF는 int로 결과가 나오므로, 이 값을 double로 바꿔야 한다.

그리고 이 값을 int인 denominator로 나누더라도, 결과는 double인 x에 저장되므로 자동으로 type casting이 이루어진다.

 

두 번째로 쓰이는 곳은, x와 y값을 계산하는 과정에서 long long으로 바꿔줘야 한다는 것이다.

바꾸지 않으면 29번 테스트케이스만 틀리는 경험을 할 수 있다.(맞왜틀..)