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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87377

문제 풀이 흐름

1. 모든 직선 쌍에 대해 반복
   A. 교점 좌표 구하기
   B. 좌표가 정수인 교점만 저장
2. 저장된 교점들에 대한 x, y좌표의 범위를 구함
3. StringBuilder 배열로 정답 구하기
4. StringBuilder 배열을 String 배열로 변환

import java.util.*;

class Solution {
    public final Set<IntersectionPoint> points = new HashSet<>();
    
    public String[] solution(int[][] line) {
        String[] answer = {};
        for (int[] line1 : line) {
            for (int[] line2 : line) {
                IntersectionPoint point = this.getIntersectionPoint(line1, line2);
                if (point == null) continue;
                this.addIntersectionPoint(point);
            }
        }
        answer = plot(this.points);
        return answer;
    }
    
    private static class IntersectionPoint {
        public final int x, y;
        
        public IntersectionPoint(int x, int y) {
            this.x = x;
            this.y = y;
        }
        
        public boolean equals(Object o) {
            if (!(o instanceof IntersectionPoint)) return false;
            IntersectionPoint i = (IntersectionPoint)o;
            return this.x == i.x && this.y == i.y;
        }
        
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
    
    private static class Range {
        public final int minX, minY, maxX, maxY;
        
        public Range(int minX, int minY, int maxX, int maxY) {
            this.minX = minX;
            this.minY = minY;
            this.maxX = maxX;
            this.maxY = maxY;
        }
        
        public static Range createRange(Set<IntersectionPoint> points) {
            int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
            int maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
            
            for (IntersectionPoint p : points) {
                minX = Integer.min(minX, p.x);
                minY = Integer.min(minY, p.y);
                maxX = Integer.max(maxX, p.x);
                maxY = Integer.max(maxY, p.y);
            }
            
            return new Range(minX, minY, maxX, maxY);
        }
    }
    
    private IntersectionPoint getIntersectionPoint(int[] line1, int[] line2) {
        long A = line1[0], B = line1[1], E = line1[2];
        long C = line2[0], D = line2[1], F = line2[2];
        long determinent1 = A * D - B * C;
        long determinent2 = B * F - E * D;
        long determinent3 = E * C - A * F;
        
        if (determinent1 == 0 || determinent2 % determinent1 != 0 || determinent3 % determinent1 != 0) return null;
        return new IntersectionPoint((int) (determinent2 / determinent1), (int) (determinent3 / determinent1));
    }
    
    private void addIntersectionPoint(IntersectionPoint point) {
        this.points.add(point);
    }
    
    private static String[] plot(Set<IntersectionPoint> points) {
        if (points.isEmpty()) return new String[] {};
        
        Range r = Range.createRange(points);
        int sizeX = r.maxX - r.minX + 1;
        int sizeY = r.maxY - r.minY + 1;
        StringBuilder[] square = new StringBuilder[sizeY];
        for (int i = 0; i < sizeY; i++) {
            square[i] = new StringBuilder(".".repeat(sizeX));
        }
        for (IntersectionPoint p : points) {
            square[r.maxY - p.y].setCharAt(p.x - r.minX, '*');
        }
        return Arrays.stream(square)
            .map(sb -> sb.toString())
            .toArray(String[]::new);
    }
}

Set<IntersectionPoint> points에 중복된 값을 가진 객체가 여러 개 들어가는 것을 방지하기 위해 IntersectionPoint 클래스에 equals와 hashCode를 오버라이드 했다.

그리고, 행렬식(Determinent)를 구할 때, $10^5 \times 10^5 = 10^{10}$으로 int의 표현 범위를 넘어서기 때문에 long을 사용했다.

코드를 더 깔끔하게 다듬어보면 다음과 같아진다.

import java.util.*;

class Solution {
    private static class Point {
        public final long x, y;
        
        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }
    
    private Point intersection(long a1, long b1, long c1, long a2, long b2, long c2) {
        double x = (double) (b1 * c2 - c1 * b2) / (a1 * b2 - b1 * a2);
        double y = (double) (c1 * a2 - a1 * c2) / (a1 * b2 - b1 * a2);
        if (x % 1 != 0 || y % 1 != 0) return null; // 좌표가 정수임을 확인
        return new Point((long) x, (long) y);
    }
    
    private Point getMinimumPoint(List<Point> points) {
        long x = Long.MAX_VALUE;
        long y = Long.MAX_VALUE;
        
        for (Point p : points) {
            x = Long.min(x, p.x);
            y = Long.min(y, p.y);
        }
        
        return new Point(x, y);
    }
    
    private Point getMaximumPoint(List<Point> points) {
        long x = Long.MIN_VALUE;
        long y = Long.MIN_VALUE;
        
        for (Point p : points) {
            x = Long.max(x, p.x);
            y = Long.max(y, p.y);
        }
        
        return new Point(x, y);
    }
    
    public String[] solution(int[][] line) {
        List<Point> points = new ArrayList<>();
        for (int i = 0; i < line.length; i++) {
            for (int j = i + 1; j < line.length; j++) {
                Point intersection = intersection(line[i][0], line[i][1], line[i][2], 
                                                  line[j][0], line[j][1], line[j][2]);
                if (intersection != null) {                    
                    points.add(intersection);
                }
            }
        }
        
        Point minimum = getMinimumPoint(points);
        Point maximum = getMaximumPoint(points);
        
        int width = (int) (maximum.x - minimum.x + 1);
        int height = (int) (maximum.y - minimum.y + 1);
        
        char[][] arr = new char[height][width];
        for (char[] row : arr) {
            Arrays.fill(row, '.');
        }
        
        for (Point p : points) {
            int x = (int) (p.x - minimum.x);
            int y = (int) (maximum.y - p.y);
            arr[y][x] = '*';
        }
        
        String[] answer = new String[arr.length];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = new String(arr[i]);
        }
        return answer;
    }
}