[programmers] 교점에 별 만들기

27 Apr 2023 in Algorithm on Algorithm

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

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        Set<Point> points = new HashSet<>();

        long minX = Long.MAX_VALUE;
        long maxX = Long.MIN_VALUE;
        long minY = Long.MAX_VALUE;
        long maxY = Long.MIN_VALUE;

        // 1. 모든 선분 조합에 대해 교점 찾기
        for (int i = 0; i < line.length; i++) {
            for (int j = i + 1; j < line.length; j++) {
                long a1 = line[i][0];
                long b1 = line[i][1];
                long c1 = line[i][2];

                long a2 = line[j][0];
                long b2 = line[j][1];
                long c2 = line[j][2];

                long denominator = a1 * b2 - a2 * b1;

                if (denominator == 0) {
                    continue; // 평행하거나 일치
                }

                long xNumerator = b1 * c2 - b2 * c1;
                long yNumerator = c1 * a2 - c2 * a1;

                if (xNumerator % denominator != 0 || yNumerator % denominator != 0) {
                    continue; // 정수가 아님
                }

                long x = xNumerator / denominator;
                long y = yNumerator / denominator;

                points.add(new Point(x, y));

                minX = Math.min(minX, x);
                maxX = Math.max(maxX, x);
                minY = Math.min(minY, y);
                maxY = Math.max(maxY, y);
            }
        }

        int width = (int)(maxX - minX + 1);
        int height = (int)(maxY - minY + 1);

        // 2. 별 찍기용 배열
        char[][] map = new char[height][width];
        for (char[] row : map) {
            Arrays.fill(row, '.');
        }

        for (Point p : points) {
            int x = (int)(p.x - minX);
            int y = (int)(maxY - p.y); // y축 방향 반대
            map[y][x] = '*';
        }

        // 3. 배열을 문자열 배열로 변환
        String[] result = new String[height];
        for (int i = 0; i < height; i++) {
            result[i] = new String(map[i]);
        }

        return result;
    }

    // 좌표 객체
    static class Point {
        long x, y;

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

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Point)) return false;
            Point p = (Point) obj;
            return x == p.x && y == p.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}