[Programmers Lv.2][교점에 별 찍기][java]

https://school.programmers.co.kr/learn/courses/30/lessons/87377?language=java 

프로그래머스

---

조건

1. line
   행 길이 - 2 이상 1000 이하
   열 길이 - 3
2. result
   1000 * 1000 이내
   별이 한 개 이상 그려짐

알고리즘

1. 두 직선 끼리의 교점 구하기 if) 겹치는 교점이 있다면? ex. 세 직선의 교점이 하나이거나 if) 교점이 없다면? ad - bc = 0 일 때 → 두 선이 평행일 때, 일치할 때
2. 교점 리스트 중 최대 x, y, 최소 x, y 구하기
3. ‘*’ 과 ‘.’ 로 리스트에 저장 (출력 형태 맞추기)

---

package com.example.javaproject3.psstudy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution87377 {
    private static class Point {
        long x, y;

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

    List<Point> intersectionPoint = new ArrayList<>();
    Long minX = Long.MAX_VALUE;
    Long minY = Long.MAX_VALUE;
    Long maxX = Long.MIN_VALUE;
    Long maxY = Long.MIN_VALUE;

    public String[] solution(int[][] line) {

        // 1. 직선 별로 교점을 찾아 리스트에 저장
        for (int i = 0; i < line.length - 1; i++) {
            for (int j = i + 1; j < line.length; j++) {
                IntersectionPoint(line[i], line[j]);
            }
        }

        // 2. 최소, 최대 point 찾기
        for (Point p : intersectionPoint) {
            minX = Math.min(minX, p.x);
            minY = Math.min(minY, p.y);
            maxX = Math.max(maxX, p.x);
            maxY = Math.max(maxY, p.y);
        }

        // 3. 출력 형태로 변환
        String[] answer = new String[(int) (maxY - minY + 1)];  // height
        boolean[][] board = new boolean[(int) (maxY - minY + 1)][(int) (maxX - minX + 1)];  // height, width

        for (Point p : intersectionPoint) {
            int x = (int) (p.x - minX);
            int y = (int) (maxY - p.y);
            board[y][x] = true;
        }

        int i = 0;
        for (boolean[] booleans : board) {
            StringBuilder sb = new StringBuilder();
            for (boolean b : booleans) {
                if (b) sb.append("*");
                else sb.append(".");
            }
            answer[i++] = sb.toString();
        }
        return answer;
    }

    public void IntersectionPoint(int[] line1, int[] line2) {  // line1 = A B E, line2 = C D F
        long denominator = (long) line1[0] * (long) line2[1] - (long) line1[1] * (long) line2[0];

        if (denominator != 0) {  // ad - bc = 0 인 경우
            long numX = (long) line1[1] * (long) line2[2] - (long) line1[2] * (long) line2[1];
            long numY = (long) line1[2] * (long) line2[0] - (long) line1[0] * (long) line2[2];

            double x = (double) numX / (double) denominator;
            double y = (double) numY / (double) denominator;

            if (x % 1 == 0 && y % 1 == 0)  // 교점이 정수면 리턴
                intersectionPoint.add(new Point((long) x, (long) y));
        }
    }

    public static void main(String[] args) {
        Solution87377 solution87377 = new Solution87377();
        int[][] line = {{2, -1, 4}, {-2, -1, 4}, {0, -1, 1}, {5, -8, -12}, {5, 8, 12}};
        String[] s = solution87377.solution(line);
        for (int i = 0; i < s.length; i++) {
            System.out.println(s[i]);
        }
//        solution87377.IntersectionPoint(new int[]{2, -1, 4}, new int[]{-2, -1, 4});
    }

}

곱셈 과정에서 Long 자료형으로 변경