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

프로그래머스

 

예시

 

참고 사항

 

• 직선 n개 중에서 2개씩 뽑아서 해당 두 직선의 교점을 구해야함
• 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않음 
• 모든 직선 쌍은 교점이 유일하게 존재하거나 평행함
• 문제 아래의 참고 사항에서 두 직선이 평행한지와 두 직선의 교점을 구하는 방법이 나와있으므로 참고하면 됨
• 모든 직선쌍의 교점을 구한 뒤 해당 영역을 그리기 위해 가장 작은 x, y 좌표와 가장 큰 x, y 좌표를 구해야함
• 이후 maxX - minX, maxY - minY가 그릴 영역의 가로, 세로가 됨
• 영역을 그린 뒤 그래프의 좌표와 그린 영역의 좌표가 다른 것을 감안해 좌표이동을 하여 '*'을 해당 좌표에 삽입

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<vector<int>> line) {
    vector<string> answer;
    vector<pair<int, int>> coor;
    // minX, maxX, minY, maxY 초기화
    int minX = INT32_MAX, maxX = INT32_MIN, minY = INT32_MAX, maxY = INT32_MIN;
    
    for(int i = 0; i < line.size(); i++) {
        for(int j = i + 1; j < line.size(); j++) {
            
            // 이 값이 0이면 두 직선은 평행
            int isParallel = line[i][0] * line[j][1] - line[i][1] * line[j][0];
            
            // 0이 아니면 교점이 존재
            if(isParallel) {
                long long x = (1LL * line[i][1] * line[j][2] - 1LL * line[i][2] * line[j][1]);
                long long y = (1LL * line[i][2] * line[j][0] - 1LL * line[i][0] * line[j][2]);
                
                // 이 중 정수로만 표현되는 좌표를 저장    
                if(x % isParallel == 0 && y % isParallel == 0) coor.push_back({x / isParallel, y / isParallel});
            }
        }
    }
    
    // 정렬 후 중복되는 좌표 제거
    sort(coor.begin(), coor.end());
    coor.erase(unique(coor.begin(), coor.end()), coor.end());
    
    // minX, maxX, minY, maxY를 구함
    for(int i = 0; i < coor.size(); i++) {
        minX = min(minX, coor[i].first);
        maxX = max(maxX, coor[i].first);
        minY = min(minY, coor[i].second);
        maxY = max(maxY, coor[i].second);
    }
    
    // 각각 영역의 가로, 세로
    int x = maxX - minX, y = maxY - minY;
    
    // 해당 영역의 크기만큼 answer를 '.'로 초기화
    for(int i = 0; i <= y; i++) {
        string board(x + 1, '.');
        answer.push_back(board);
    }
    
    // 좌표이동 후 '*'를 삽입
    for(int i = 0; i < coor.size(); i++) 
        answer[maxY - coor[i].second][coor[i].first - minX] = '*';
    
    return answer;
}