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

프로그래머스: 문제

코딩테스트 연습 - 10주차

상당히 쉽다고 생각했던 문제였는데 푸는 데 꽤 걸렸고, 힌트를 사용할 수 밖에 없었다. 우선 중복적으로 교점이 생기는 가능성을 고려하지 않아서 로직에 누수가 발생했고, 자료형을 처리하는 데 어려움을 느꼈다. 그래도 별의 위치값을 y값 내림차순, x값 오름차순으로 정렬한 후 구간을 정해서 상대적인 위치로 문자를 삽입한 일은 잘 처리했다고 생각한다.

 

틀렸던 부분을 복기해보자면

1. 자료형

2. MAX 값

 

자료형을 처음에는 int형만 썼는데 long long을 써야 한다.

왜냐하면 x와 y 각각 최대값으로 $$10^{5 + 5}$$이다. 왜냐하면 A부터 F까지의 최댓값이 각각 10,000이기 때문이다. 그래서 분모가 최소 1인 경우를 가정하여 최대치를 1e10으로 설정하고 최솟값은 -1 * 1e10으로 설정하였다.

여기서 e를 써서 지수형태인 1e10(1에 10의 10제곱을 곱한 수)으로 최대치를 표현했다. 그리고 자료형태는 long long으로 처리해서 overflow를 방지한다. 특히 주어지는 int형의 계수들을 long long으로 변환해야 연산과정에서 overflow를 방지할 수 있다. 

 

그리고 주어진 별들의 위치를 y 내림차순, x 오름차순으로 정렬한 다음에 구간을 순회하면서 해당 위치에 별을 표시한다. 이때 답으로 return할 answer vector 내의 string은 상대적 위치로 인덱싱을 처리해야 한다. 그래서 전체적인 구간의 너비와 높이를 구한다. 그리고 x값에서 minx를 더하고, y값에서 maxy를 빼면 해당 별의 현재 구간 내 상대적인 위치를 구할 수 있다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#define MAX 1e10
using namespace std;
bool cmp(const pair<long long,long long> &a, const pair<long long,long long> &b){
    if(a.second == b.second){
        return a.first < b.first;
    }
    return a.second > b.second;
}

vector<string> solution(vector<vector<int>> line) {
    vector<string> answer;
    vector<pair<long long, long long>> stars;
    long long a,b,c,d,e,f;
    double x, y;
    long long maxx = -1 * MAX, maxy = -1 * MAX;
    long long minx = MAX, miny = MAX;
    for(int i = 0;i < line.size();i++){
        a = line[i][0];
        b = line[i][1];
        e = line[i][2];
        for(int j = i + 1;j < line.size();j++){
            c = line[j][0];
            d = line[j][1];
            f = line[j][2];
            long long den = a * d - b * c;
            if(!den) continue;
            x = (double)(b * f - e * d) / den;
            y = (double)(e * c - a * f) / den;
            if(x != (long long) x || y != (long long) y) continue;
            maxx = max(maxx, (long long)x);
            maxy = max(maxy, (long long)y);
            minx = min(minx, (long long)x);
            miny = min(miny, (long long)y);
            if(find(stars.begin(), stars.end(), make_pair((long long)x,(long long)y)) != stars.end()) continue;
            stars.push_back({x,y});
        }
    }
    sort(stars.begin(), stars.end(), cmp);
    int width = maxx - minx + 1;
    int height = maxy - miny + 1;
    int s = 0;
    for(int h = 0;h < height;h++){
        string str = "";
        for(int w = 0;w < width;w++){
            if(stars[s].first == minx + w && stars[s].second == maxy - h){
                str += "*";
                s++;
            }
            else{
                str += ".";
            }
        }
        answer.push_back(str);
    }
    return answer;
}