[프로그래머스 lv2] 교점에 별 만들기 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

line의 원소 개수가 1000개 이하이므로, 두 직선을 선택하여 가능한 모든 교점을 구해도 TLE가 발생하지 않는다.

두 개의 직선에 대하여 교점 (x, y)를 구한 뒤 중복없이 원소를 저장하는 set에 넣어놓자. (x는 세로, y는 가로)

 

교점을 포함하는 좌표평면을 리턴할 때, 교점의 최솟값과 최댓값을 감싸는 범위 내에서만 좌표평면을 구성하면 된다.

교점의 x좌표와 y좌표에 대해 각각 최댓값, 최솟값을 구한 후, 해당 크기만큼의 보드를 만들자.

교점 (x, y)는 새로운 보드에서 (mnx-x, y-mny)가 되므로 해당 위치에 표시하여 리턴하면 정답이다.

 

 

 

주의 할 것

좌표를 구하는 과정에서 int 범위를 넘어갈 수 있기 때문에 long long 자료형을 사용해야한다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using l = long long;
using ll = pair<l, l>;

#define X first
#define Y second

vector<string> solution(vector<vector<int>> line) {
    
    int n = line.size();

    //2개 직선을 선택하여 가능한 모든 교점 구하기
    set<ll> st;
    l A, B, C, D, E, F;

    for (int i=0; i<n-1; i++) {
        for (int j=i+1; j<n; j++) {
            A = line[i][0], B = line[i][1], E = line[i][2];
            C = line[j][0], D = line[j][1], F = line[j][2];
            if (A*D-B*C != 0) {
                if ((B*F-E*D)%(A*D-B*C) == 0 && (E*C-A*F)%(A*D-B*C) == 0)
                    st.insert({(E*C-A*F)/(A*D-B*C), (B*F-E*D)/(A*D-B*C)});
            }
        }
    }
    
    //교점을 좌표에 나타내기
    l mnx = LLONG_MAX, mny = LLONG_MAX;
    l mxx = LLONG_MIN, mxy = LLONG_MIN;
    
    for (auto [x, y] : st) {
        mnx = min(mnx, x);
        mxx = max(mxx, x);
        mny = min(mny, y);
        mxy = max(mxy, y);
    }

    vector<string> ans(mxx-mnx+1, string(mxy-mny+1, '.'));    
    for (auto [x, y] : st) ans[mxx-x][y-mny] = '*'; 
    return ans;
}