TIL - day39

알고리즘

프로그래머스 - Lv.2 교점에 별 만들기

교점에 별 만들기

1. 정수교점을 구한다.
2. 출력의 가로 세로를 구한다.
3. 출력.

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        Set<Meet> meets = intMeets(line);

        return print(meets);
    }

    public String[] print(Set<Meet> meets) {
        int xOffset, yOffset, xLimit, yLimit;
        int[] area = getField(meets);

        xOffset = area[0];
        yOffset = area[1];
        xLimit = area[2];
        yLimit = area[3];

        // -4,-4 => (0,4) 는 (4, 0) 즉, x는 xoffset만큼 빼기, y는 yoffset만큼 더하기
        // 스캔범위 (0,0) ~ (xLimit,yLimit)
        // 좌표계 변환 (1,1)은 기존에서 왼쪽으로 xOffset만큼, 위로 yOffset만큼
        // (0,0)은 원래 (-4,4)였다 원래대로 하려면 -4를 하고 4를 더한다.
        // 좌표에 xOffset을 더하고 yOffset을 빼면 기존 좌표가 나옴
        String[] res = new String[yOffset - yLimit + 1];
        for (int y = 0; y <= yOffset - yLimit; y++) {
            StringBuilder sb = new StringBuilder();

            for (int x = 0; x <= xLimit - xOffset; x++) {
                int originX = x + xOffset;
                int originY = -y + yOffset;
                if (meets.contains(new Meet(originX, originY))) {
                    sb.append('*');
                } else {
                    sb.append('.');
                }
            }

            res[y] = sb.toString();
        }

        return res;
    }

    public int[] getField(Set<Meet> meets) {
        int xOffset = Integer.MAX_VALUE, yOffset = Integer.MIN_VALUE,
                xLimit = Integer.MIN_VALUE, yLimit = Integer.MAX_VALUE;

        for (Meet meet : meets) {
            xOffset = Math.min(xOffset, meet.x);
            yOffset = Math.max(yOffset, meet.y);
            xLimit = Math.max(xLimit, meet.x);
            yLimit = Math.min(yLimit, meet.y);
        }

        return new int[]{xOffset, yOffset, xLimit, yLimit};
    }

    public Set<Meet> intMeets(int[][] line) {
        Set<Meet> meets = new HashSet<>();
        for (int i = 0; i < line.length; i++) {
            for (int j = i + 1; j < line.length; j++) {
                Meet meet = getMeet(line[i], line[j]);
                if (meet != null) {
                    meets.add(meet);
                }
            }
        }
        return meets;
    }

    public Meet getMeet(int[] line1, int[] line2) {
        long a, b, c, d, e, f;
        a = line1[0];
        b = line1[1];
        c = line2[0];
        d = line2[1];
        e = line1[2];
        f = line2[2];


        long parent = a * d - b * c;
        if (parent == 0) {
            return null;
        }

        long xChild = b * f - e * d;
        long yChild = e * c - a * f;

        if (xChild % parent != 0 || yChild % parent != 0) {
            return null;
        }

        return new Meet((int)(xChild / parent), (int)(yChild / parent));
    }

    static class Meet {
        int x;
        int y;

        public Meet(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Meet meet = (Meet) o;
            return x == meet.x && y == meet.y;
        }

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