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

---

📌 문제 설명

Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.

예를 들어, 다음과 같은 직선 5개를

• 2x - y + 4 = 0
• -2x - y + 4 = 0
• -y + 1 = 0
• 5x - 8y - 12 = 0
• 5x + 8y + 12 = 0

좌표 평면 위에 그리면 아래 그림과 같습니다.

이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)입니다.

만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.

위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다.

"..........."
".....*....."
"..........."
"..........."
".*.......*."
"..........."
"..........."
"..........."
"..........."
".*.......*."
"..........."

이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.

따라서 정답은

"....*...."
"........."
"........."
"*.......*"
"........."
"........."
"........."
"........."
"*.......*"

 

입니다.

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

 

📌 제한 사항

• line의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다.
  • line의 가로(열) 길이는 3입니다.
  • line의 각 원소는 [A, B, C] 형태입니다.
  • A, B, C는 -100,000 이상 100,000 이하인 정수입니다.
  • 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
  • A = 0이면서 B = 0인 경우는 주어지지 않습니다.
• 정답은 1,000 * 1,000 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
#include <climits>

using namespace std;

pair<long long, long long> getIntersectionPoint(const vector<int> &a, const vector<int> &b){
    long long A = a[0], B = a[1], E = a[2];
    long long C = b[0], D = b[1], F = b[2];
    
    long long denominator = A * D - B * C;
    
    if (denominator == 0) {
        return {LLONG_MAX, LLONG_MAX};
    }
    
    long long xNumerator = B * F - D * E;
    long long yNumerator = C * E - A * F;
    
    if (xNumerator % denominator != 0 || yNumerator % denominator != 0) {
        return {LLONG_MAX, LLONG_MAX};
    }
    
    long long x = xNumerator / denominator;
    long long y = yNumerator / denominator;
    
    return {x, y};
}

vector<string> solution(vector<vector<int>> line) {
    set<pair<long long, long long>> points;
    
    for (int i = 0; i < line.size(); i++) {
        for (int j = i + 1; j < line.size(); j++) {
            pair<long long, long long> intersection = getIntersectionPoint(line[i], line[j]);
            
            if (intersection.first != LLONG_MAX && intersection.second != LLONG_MAX) {
                points.insert(intersection);
            }
        }
    }

    long long minX = LLONG_MAX;
    long long maxX = LLONG_MIN;
    long long minY = LLONG_MAX;
    long long maxY = LLONG_MIN;
    
    for (const auto& point : points) {
        minX = min(minX, point.first);
        maxX = max(maxX, point.first);
        minY = min(minY, point.second);
        maxY = max(maxY, point.second);
    }
    
    int width = maxX - minX + 1;
    int height = maxY - minY + 1;
    vector<string> answer(height, string(width, '.'));
    
    for (const auto& point : points) {
        int x = point.first - minX;
        int y = maxY - point.second;
        answer[y][x] = '*';
    }
    
    return answer;
}

---

📝 풀이

중복을 피하기 위해 set에 모든 직선의 조합에서 그려야 할 정수로된 교점을 저장합니다.

직선 사이의 교점을 구해주는 getIntersectionPoint 함수를 호출합니다.

 

getIntersectionPoint 함수는 두 직선 사이에 교점이 없거나 정수가 아닐 경우에 LLONG_MAX 쌍을 반환합니다.

교점이 모두 정수인 경우 좌표를 반환합니다.

 

별표를 그리기 위해 x와 y 좌표의 최솟값과 최댓값을 찾습니다.

최솟값과 최댓값을 이용하여 그릴 사각형의 너비와 길이를 초기화합니다.

0인 경우도 존재하니 1을 추가로 더해줍니다.

각 교점의 위치에 '*'을 표시합니다.

 

최종적으로 별이 그려진 사각형의 정보 answer을 return 합니다.