📖 문제

문제 설명

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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

---

✍ 입출력 예

입출력 예

line	result
[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]	["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]
[[0, 1, -1], [1, 0, -1], [1, 0, 1]]	["*.*"]
[[1, -1, 0], [2, -1, 0]]	["*"]
[[1, -1, 0], [2, -1, 0], [4, -1, 0]]	["*"]

✅ 코드

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        List<Point> pointList = new ArrayList<>();
        
        // 모든 교점 계산
        for (int i = 0; i < line.length - 1; i++) {
            for (int j = i + 1; j < line.length; j++) {
                Point point = getPoint(line[i][0], line[i][1], line[i][2], line[j][0], line[j][1], line[j][2]);
                if (point != null) {
                    pointList.add(point);
                }
            }
        }

        // 교점이 없는 경우
        // if (pointList.isEmpty()) return new String[0];

        // 범위 찾기
        long minX = Long.MAX_VALUE;
        long maxX = Long.MIN_VALUE;
        long minY = Long.MAX_VALUE;
        long maxY = Long.MIN_VALUE;
        
        for (Point point : pointList) {
            minX = Math.min(minX, point.x);
            maxX = Math.max(maxX, point.x);
            minY = Math.min(minY, point.y);
            maxY = Math.max(maxY, point.y);
        }

        int width = (int)(maxX - minX + 1);
        int height = (int)(maxY - minY + 1);
        
        // 2차원 배열 초기화 (빈 공간으로)
        char[][] starArr = new char[height][width];
        for (char[] row : starArr) {
            Arrays.fill(row, '.');
        }

        // 별 좌표 설정
        for (Point point : pointList) {
            int y = (int)(maxY - point.y);
            int x = (int)(point.x - minX);
            starArr[y][x] = '*';
        }
        
        // 결과 배열 변환
        String[] answer = new String[height];
        for (int i = 0; i < height; i++) {
            answer[i] = new String(starArr[i]);
        }
        
        return answer;
    }
    
    // 교점 찾기
    public static Point getPoint(long a, long b, long c, long d, long e, long f) {
        long denominator = (a * e) - (b * d);    // 분모
        long numeratorX = (b * f) - (c * e);     // 분자 x
        long numeratorY = (c * d) - (a * f);     // 분자 y

        // 1. 분모 값이 0이면 두 직선이 평행이기 때문에 교점이 없으므로 null
        // 2. 정확히 나누어 떨어지는 경우만 반환
        if(denominator == 0 || numeratorX % denominator != 0 || numeratorY % denominator != 0) { return null; }

        long x = numeratorX / denominator;
        long y = numeratorY / denominator;

        return new Point(x, y);
    }
}


class Point {
    long x;
    long y;

    Point(long x, long y) {
        this.x = x;
        this.y = y;
    }
}