[Java] 2021 위클리 챌린지 10주차 - 교점에 별 만들기

 

 

직선의 교점 중 정수가 되는 교점에 * 모양으로 표시하고, 이 별들을 포함하는 최소한의 사각형을 만들어서 출력하는 것이 문제이다.

먼저 정수가 되는 교점을 찾아야된다. 문제에서 친절하게 교점을 구하는 식을 알려주었다.

$$Ax + By + E = 0$$ $$Cx + Dy + F = 0$$

$$ x = {BF - ED \over AD -BC}, y = {EC - AF \over AD -BC}$$

이 식을 이용해서 교점을 구하면 된다. 단, AD-BC가 0인 경우에는 두직선이 평행하는 경우로 제외해준다. 

그리고 나머지 연산을 이용해서 딱 나누어 떨어지는지를 체크하고, 정수의 교점만 찾는 것이기 때문에 딱 나누어 떨어지지 않으면 마찬가지로 제외해준다.

이렇게 구한 교점들을 배열에 넣어서 저장하고, 각각의 x와 y의 최대 최소값을 구한다.

좌표계에서 x방향으로의 증가는 2차원 배열에서 열로 값이 증가하는 것을 의미한다. 그래서 열의 index는 x - minX 가 된다. 

반면 y방향으로의 증가는 행의 값의 감소를 의미한다. 그래서 행의 index는 maxY - y 가 된다. 

미리 점(.)들로 answer를 채워 놓은 다음에 찾은 교점들을 순회하면서 점들을 별(*)로 바꿔주면 정답이 된다.

※주의 : a,b,c,d,e,f를 long으로 지정하자. 안그러면 int overflow가 발생하여 틀린 정답이 된다. 

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

class Point {
    long x;
    long y;

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

class Solution {
    public String[] solution(int[][] line) {
        String[] answer = {};
        int n = line.length;
        List<Point> points = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long a = line[i][0];
                long b = line[i][1];
                long e = line[i][2];
                long c = line[j][0];
                long d = line[j][1];
                long f = line[j][2];
                long adbc = a * d - b * c;
                if (adbc == 0) {
                    continue;
                }
                long bfed = b * f - e * d;
                if (bfed % adbc != 0) {
                    continue;
                }
                long ecaf = e * c - a * f;
                if (ecaf % adbc != 0) {
                    continue;
                }
                long x = bfed / adbc;
                long y = ecaf / adbc;
                points.add(new Point(x, y));
            }
        }
        long minX = points.get(0).x;
        long minY = points.get(0).y;
        long maxX = points.get(0).x;
        long maxY = points.get(0).y;

        points.stream().forEach(a -> {
            System.out.println(a.x + " " + a.y);

        });
        for (int i = 0; i < points.size(); i++) {
            Point p = points.get(i);
            minX = Math.min(minX, p.x);
            minY = Math.min(minY, p.y);
            maxX = Math.max(maxX, p.x);
            maxY = Math.max(maxY, p.y);
        }
        long width = maxX - minX + 1;
        long height = maxY - minY + 1;
        StringBuilder sb = new StringBuilder();
        answer = new String[(int) height];
        for (int i = 0; i < width; i++) {
            sb.append(".");
        }
        for (int i = 0; i < height; i++) {
            answer[i] = sb.toString();
        }
        for (int k = 0; k < points.size(); k++) {
            Point p = points.get(k);
            long j = p.x - minX;
            long i = maxY - p.y;
            answer[(int) i] = answer[(int) i].substring(0, (int) j) + "*" + answer[(int) i].substring((int) (j + 1));
        }
        return answer;
    }
}