교점에 별 만들기

문제

Ax + By + C = 0 형태로 표현되는 여러 직선의 방정식 계수들이 2차원 배열 line으로 주어집니다.

모든 직선 쌍의 교점을 구하고, 그중 x좌표와 y좌표가 모두 '정수'인 교점들에만 별(*)을 그립니다.

이 별들을 모두 포함하는 가장 작은 사각형 형태의 격자판(빈 공간은 .)을 문자열 배열로 반환하는 문제입니다.

• 교점을 구하는 수학 공식은 문제에서 제공됩니다.
  • x = (BF - CE) / (AE - BD)
  • y = (CD - AF) / (AE - BD)

풀이: 교점 계산 및 2차원 배열 매핑

이 문제는 주어진 수학 공식을 코드로 오차 없이 구현하고, 좌표 평면을 2차원 배열의 인덱스로 변환하는 능력을 묻는 구현 문제입니다.

1. 오버플로우 방지: 제공된 교점 공식을 계산할 때 곱셈이 빈번하게 발생합니다. 계수 값이 크면 int 범위를 쉽게 초과하므로, 계산되는 분모와 분자는 모두 long 타입으로 처리해야 합니다. 또한, 최댓값/최솟값을 담는 한계점 변수들도 long으로 선언해야 합니다.
2. 정수 교점 판별: 분모가 0이면 두 직선은 평행하거나 일치하므로 무시합니다. 분모가 0이 아닐 때 분자를 분모로 나누어 떨어지는지(나머지가 0인지) 확인하여 정수 교점만 골라 리스트에 저장합니다. 문제에 주어진 공식의 변수(A, B, C, D, E, F)를 그대로 사용하여 구현했습니다.
3. 격자판 크기 구하기: 리스트에 모인 모든 정수 교점들을 순회하며 minX, maxX, minY, maxY를 구합니다.
4. 격자판의 너비는 maxX - minX + 1, 높이는 maxY - minY + 1이 됩니다.
5. 좌표를 배열 인덱스로 변환:
   • 수학의 좌표 평면과 2차원 배열의 인덱스는 방향이 다릅니다.
   • x좌표는 커질수록 오른쪽으로 가므로 열(column) 인덱스와 방향이 같아 p.x - minX로 단순 치환합니다.
   • y좌표는 커질수록 위쪽으로 가지만, 행(row) 인덱스는 커질수록 아래쪽을 향합니다. 따라서 배열의 최상단(0번 행)에 maxY가 위치해야 하므로 maxY - p.y로 인덱스를 뒤집어 주어야 합니다.

코드 1: 교점 계산 및 2차원 배열 매핑

import java.util.*;

class Solution {
    class Point {
        long x, y;

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

    List<Point> list = new ArrayList<>();

    public String[] solution(int[][] line) {
        // 1. 모든 직선 쌍의 교점 구하기
        for (int i = 0; i < line.length - 1; i++) {
            for (int j = i + 1; j < line.length; j++)
                getPoint(line[i], line[j]);
        }

        // 2. 좌표의 최댓값, 최솟값 초기화 및 갱신
        long minX = Long.MAX_VALUE, minY = Long.MAX_VALUE;
        long maxX = Long.MIN_VALUE, maxY = Long.MIN_VALUE;

        for (Point p : list) {
            minX = Math.min(minX, p.x);
            maxX = Math.max(maxX, p.x);
            minY = Math.min(minY, p.y);
            maxY = Math.max(maxY, p.y);
        }

        // 격자판 크기 계산
        int w = (int) (maxX - minX + 1);
        int h = (int) (maxY - minY + 1);

        char[][] map = new char[h][w];
        for (int i = 0; i < h; i++)
            Arrays.fill(map[i], '.');

        // 3. 2차원 배열 인덱스로 매핑하여 별 찍기
        for (Point p : list) {
            int y = (int) (maxY - p.y);
            int x = (int) (p.x - minX);
            map[y][x] = '*';
        }

        // 4. 문자열 배열로 변환
        String[] ans = new String[h];
        for (int i = 0; i < h; i++)
            ans[i] = new String(map[i]);

        return ans;
    }

    void getPoint(int[] l1, int[] l2) {
        long A = l1[0], B = l1[1], C = l1[2];
        long D = l2[0], E = l2[1], F = l2[2];

        long denom = A * E - B * D;
        if(denom == 0) return;

        long numX = B * F - C * E;
        long numY = C * D - A * F;

        // 나누어 떨어지면 정수 좌표이므로 리스트에 추가
        if (numX % denom == 0 && numY % denom == 0)
            list.add(new Point(numX / denom, numY / denom));
    }
}