[programmers/js] 교점에 별 만들기

교점에 별 만들기

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

문제 설명

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)입니다.

위 좌표를 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 최소 크기로 나타내세요.

풀이

두 직선 Ax + By + E = 0, Cx + Dy + F = 0 이 교차하는 지점은

x = (B*F - E*D) / (A*D - B*C)
y = (E*C - A*F) / (A*D - B*C)

입니다. 이 공식을 활용하면 쉽게 해결 가능합니다.

function solution(line) {
    const points = [];
	
    const getPoint = (arr1, arr2) => {
        const [a, b, e] = arr1;
        const [c, d, f] = arr2;

        const denominator = a * d - b * c;

        // 분모가 0이면 평행이거나 일치 → 교점 없음
        if (denominator === 0) return;

        const x = (b * f - e * d) / denominator;
        const y = (e * c - a * f) / denominator;

        // 정수 교점만 저장
        if (Number.isInteger(x) && Number.isInteger(y)) {
            points.push([x, y]);
        }
    }

    const len = line.length;

    for (let i = 0; i < len - 1; i++) {
        for (let j = i + 1; j < len; j++) {
            getPoint(line[i], line[j]);
        }
    }

    // 최소, 최대 x, y 구하기
    let [minX, minY] = [Infinity, Infinity];
    let [maxX, maxY] = [-Infinity, -Infinity];

    for (const [x, y] of points) {
        minX = Math.min(minX, x);
        minY = Math.min(minY, y);
        maxX = Math.max(maxX, x);
        maxY = Math.max(maxY, y);
    }

    const width = maxX - minX + 1;
    const height = maxY - minY + 1;

    // '.'로 채운 빈 판 만들기
    const board = Array.from({ length: height }, () => Array(width).fill('.'));

    // 별 찍기
    for (const [x, y] of points) {
        const nx = x - minX;
        const ny = maxY - y; // y축 반전해서 찍어야 함
        board[ny][nx] = '*';
    }

    // 문자열 배열로 변환
    return board.map(row => row.join(''));
}