[Programmers] 위클리 챌린지 10 교점에 별 만들기

안녕하세요. 이번 포스팅에서는 위클리 챌린지 10, 교점에 별 만들기 문제를 풀어보도록 하겠습니다.

 

해당 문제는

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

코딩테스트 연습 - 10주차

 

위 링크를 통해 확인하실 수 있습니다.

 

각 직선의 모든 교점을 구하는 문제입니다. 직선의 교점을 구하는 식이 주어졌습니다.

 

저는 이 식을 이용하셔서 교점을 구했습니다.

 

이 문제를 풀 때 유의할 점이

 

1. int*int의 연산이 최대 범위에 따라 int를 넘어갈 수 있다는 것.

2. 두 교점이 모두 정수인 경우에만 판별하는 것.

3. 좌표계의 y축은 배열의 row가 증가하는 방향과 반대방향이라는 것.

 

따라서 위의 예외사항들을 하나씩 해결하며 풀어가야 합니다.

 

제가 문제를 해결한 알고리즘은 다음과 같습니다.

 

1. 두개의두 개의 for loop을 활용하여 모든 직선 두 개의 경우의 수를 구하기.

2. 위 식을 활용하여 두 직선의 교점을 구하기. 교점이 존재하고, 두 교점이 정수인 경우에만 교점 벡터에 추가하기.

 

pair<ll,ll> findCross(vector<int>& line1, vector<int>& line2) {
    pair<ll,ll> ret = {MAX, MAX};
    
    ll a = line1[0], b = line1[1], e = line1[2], c = line2[0], d = line2[1], f = line2[2];
    if((ll)a*d - (ll)b*c == 0) return ret; // 평행하다면 {MAX,MAX} return.
    
    double retX = (double)(b*f - e*d)/(double)(a*d - b*c);
    double retY = (double)(e*c - a*f)/(double)(a*d - b*c);
    if((ll)retX == retX && (ll)retY == retY) ret = {retX, retY}; // 모두 정수라면 ret = {retX, retY}
    return ret;
}

 

3. 모든 교점을 갖는 벡터에서

최소 X, 최대 X, 최소 Y, 최대 Y 구하기.

 

    ll minX = MAX, minY = MAX, maxX = -MAX, maxY = -MAX;
    for(pair<ll,ll> a : crossPoint) {
        minX = min(a.first, minX);
        minY = min(a.second, minY);
        maxX = max(a.first, maxX);
        maxY = max(a.second, maxY);
    }

 

answer 벡터를 만들기. 교점이면 '*', 교점이 아니면 '.'

 

 

<소스 코드>

#include <bits/stdc++.h>
#define MAX 100000000004

typedef long long ll;
using namespace std;

pair<ll,ll> findCross(vector<int>& line1, vector<int>& line2) {
    pair<ll,ll> ret = {MAX, MAX};
    
    ll a = line1[0], b = line1[1], e = line1[2], c = line2[0], d = line2[1], f = line2[2];
    if((ll)a*d - (ll)b*c == 0) return ret;
    
    double retX = (double)(b*f - e*d)/(double)(a*d - b*c);
    double retY = (double)(e*c - a*f)/(double)(a*d - b*c);
    if((ll)retX == retX && (ll)retY == retY) ret = {retX, retY};
    return ret;
}
vector<string> solution(vector<vector<int>> line) {
    vector<string> answer;
    set<pair<ll,ll>> crossPoint;
    
    for(int i = 0; i < line.size(); i++) {
        for(int j = i+1; j < line.size(); j++) {
            pair<ll,ll> cross = findCross(line[i], line[j]);
            if(cross.first != MAX && cross.second != MAX) crossPoint.insert(cross);
        }
    }
    ll minX = MAX, minY = MAX, maxX = -MAX, maxY = -MAX;
    for(pair<ll,ll> a : crossPoint) {
        minX = min(a.first, minX);
        minY = min(a.second, minY);
        maxX = max(a.first, maxX);
        maxY = max(a.second, maxY);
    }
    
    for(ll i = maxY; i >= minY; i--) {
        string res = "";
        for(ll j = minX; j <= maxX; j++) {
            if(crossPoint.find({j, i}) == crossPoint.end()) res+='.';
            else res+='*';
        }
        answer.push_back(res);
    }
    return answer;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.