프로그래머스 - 위클리 챌린지 10주차, 교점에 별 만들기 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/87377

코딩테스트 연습 - 교점에 별 만들기

 

문제 풀이

수학, 구현에 관련된 문제이다.

 

교점을 구하는 공식은 문제 밑의 [참고사항]에 주어져있으므로 이를 참고하여 교점을 구하는 함수를 구현한다.

이 과정에서 integer의 범위를 넘어가는 케이스가 있기 때문에 모두 타입을 long long으로 해준다.

문제에서 주어졌듯이 모든 교점이 별을 그리는 교점이 아니라 정수로 표현되는 교점만 별을 그리는 교점이다.

따라서, 분모가 0이 되는 경우(평행 또는 일치) 와 정수로 표현되지 않는 교점들은 무한대를 리턴한다. 추후에 직선의 방정식을 입력받아

무한대가 리턴되는 경우는 continue 해주면 구하고자 하는 교점만 배열에 담을 수 있다.

 

교점을 담는 자료구조는 set을 사용했다. 4번 테스트 케이스같은 경우 교점 (0, 0)만 세 번 나타나므로 불필요한 중복을 피하고자 했다.

교점을 모두 담은 다음엔 x좌표와 y좌표의 최댓값, 최솟값을 구해서 좌표의 범위를 구하여 모든 좌표에 점(.)을 추가하였다.

 

다음으로 구한 교점이 위치하는 곳에 별(*)을 찍어주면 된다. 이 때, 수학적인 규칙을 찾아야 하는데

예를 들어, 첫 번째 테스트 케이스는 answer[0][0] ~ answer[8][8]까지 존재하며

maxX = 4, minX = -4, maxY = 4, minY = -4이다.

set에 담겨있는 좌표들, 즉 우리가 구한 교점들은 (0, 4), (-4, 1), (4, 1), (-4, -4), (4, -4)이다. 

 

"....*...."

"........."

"........."

"*.......*"

"........."

"........."

"........."

"........."

"*.......*"

 

배열로 나타내면 위와 같은데 이는 우리가 알고 있는 xy좌표계와는 다르다.

우선, (0, 0)의 역할을 answer[4][4]가 하고 있으므로 각 x, y좌표에서 최솟값을 빼준다.

그러면 answer[y - minY][x - minX]의 형태가 된다.

하지만, y축은 아래로 증가하는 형태로 바뀌었으므로 거꾸로 그리기 위해 배열의 height인 maxY - minY을 더해주어야 한다.

식을 정리하면 maxY - minY - (y - minY) = maxY - y가 된다. 

즉, y좌표는 maxY - s.second, x좌표는 s.first - minX이며 모두 절댓값을 취해준다.

 

이러한 방식으로 set을 돌며 별을 찍어주면 된다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

#define INF LLONG_MAX
#define mINF LLONG_MIN
typedef long long ll;

pair<ll, ll> MeetingPoint(ll A, ll B, ll E, ll C, ll D, ll F){
    if((A*D - B*C) == 0) return make_pair(INF, INF);
    
    if ((B*F - E*D) % (A*D - B*C) != 0) return make_pair(INF, INF); 
    if ((E*C - A*F) % (A*D - B*C) != 0) return make_pair(INF, INF); 
    
    ll x = (B*F - E*D) / (A*D - B*C);
    ll y = (E*C - A*F) / (A*D - B*C);
    
    return make_pair(x, y);
}

vector<string> solution(vector<vector<int>> line) {
    set<pair<ll, ll> > s;
    vector<string> answer;
    
    for(int i=0; i<line.size() - 1; i++){
        for(int j=i+1; j<line.size(); j++){
            ll A = line[i][0];
            ll B = line[i][1];
            ll E = line[i][2];
            ll C = line[j][0];
            ll D = line[j][1];
            ll F = line[j][2];
            
            pair<ll, ll> mp = MeetingPoint(A, B, E, C, D, F);
            if(mp.first == INF) continue;
            else s.insert(mp);
        }
    }
    
    ll minX = INF, maxX = mINF;
    ll minY = INF, maxY = mINF;
    
    for(auto it = s.begin(); it != s.end(); ++it){
        if(minX > it->first) minX = it->first;
        if(minY > it->second) minY = it->second;
        if(maxX < it->first) maxX = it->first;
        if(maxY < it->second) maxY = it->second;
    }
    
    ll width = abs(maxX - minX);
    ll height = abs(maxY - minY);
    
    for(int i=0; i<height + 1; i++){
        string tmp = "";
        for(int j=0; j<width + 1; j++){
            tmp += ".";
        }
        answer.push_back(tmp);
    }
    
    for(auto it = s.begin(); it != s.end(); ++it){
        answer[abs(maxY - it->second)][abs(minX - it->first)] = '*';
    }
    
    return answer;
}