[JAVA 풀이] 프로그래머스 - 교점에 별 만들기 (Level2)

728x90

코딩테스트 연습 - 교점에 별 만들기

[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, -

programmers.co.kr

📝 문제 설명

Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.

예를 들어, 다음과 같은 직선 5개를

2x - y + 4 = 0
-2x - y + 4 = 0
-y + 1 = 0
5x - 8y - 12 = 0
5x + 8y + 12 = 0

좌표 평면 위에 그리면 아래 그림과 같습니다.

이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)입니다.

만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.

RisingStarGraphStar

위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다.

"..........."  
".....*....."  
"..........."  
"..........."  
".*.......*."  
"..........."  
"..........."  
"..........."  
"..........."  
".*.......*."  
"..........."

이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.

따라서 정답은

"....*...."  
"........."  
"........."  
"*.......*"  
"........."  
"........."  
"........."  
"........."  
"*.......*"

입니다.

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

⚠️ 제한사항

line의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다.
- line의 가로(열) 길이는 3입니다.
- line의 각 원소는 [A, B, C] 형태입니다.
- A, B, C는 -100,000 이상 100,000 이하인 정수입니다.
- 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
- A = 0이면서 B = 0인 경우는 주어지지 않습니다.
정답은 1,000 * 1,000 크기 이내에서 표현됩니다.
별이 한 개 이상 그려지는 입력만 주어집니다.

🖨 입출력 예

line	result
[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]	["........", ".........", ".........", ".......", ".........", ".........", ".........", ".........", ".......*"]
[[0, 1, -1], [1, 0, -1], [1, 0, 1]]	["."]
[[1, -1, 0], [2, -1, 0]]	["*"]
[[1, -1, 0], [2, -1, 0], [4, -1, 0]]	["*"]

📂 분류

구현

💡 풀이

문제에 나온 공식대로 모든 정수의 교점을 구한다. 여기서 교점을 구할 때 denominator가 0일 경우와 xNumerator % denominator != 0 이거나 yNumerator % denominator != 0일 경우는 리스트에 추가하지 않는다.

그다음 너비와 높이를 구하기 위해 좌표의 최댓값, 최솟값을 구한다. 그리고 별을 찍기 위해 Boolean 2차원 배열을 선언한 다음 교점들을 1사분면으로 이동시켜 true로 저장한다. 여기서 주의해야 할 점은 1사분면과 2차원 배열은 x, y 값이 바뀌기 때문에 Y = maxY - y, X = x - minX와 같이 계산해야 한다.

💻 코드

import java.util.*;

class Solution {

    private static class Point {

        long x;
        long y;

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

    List<Point> pointOfIntersection = 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) {
        String[] answer = {};

        for (int i = 0; i < line.length - 1; i++) {
            for (int j = i + 1; j < line.length; j++) {
                getPointOfIntersection(line[i], line[j]);
            }
        }

        getMinPointAndMaxPoint();

        long height = maxY - minY + 1;
        long width = maxX - minX + 1;

        answer = new String[(int) height];
        boolean[][] board = new boolean[(int) height][(int) width];

        for (Point point : pointOfIntersection) {
            int x = (int) (point.x - minX);
            int y = (int) (maxY - point.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;
    }

    private void getMinPointAndMaxPoint() {
        for (Point point : pointOfIntersection) {
            minX = Math.min(minX, point.x);
            minY = Math.min(minY, point.y);
            maxX = Math.max(maxX, point.x);
            maxY = Math.max(maxY, point.y);
        }
    }

    private void getPointOfIntersection(int[] A, int[] B) {
        long a = A[0];
        long b = A[1];
        long c = B[0];
        long d = B[1];
        long e = A[2];
        long f = B[2];

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

        long xNumerator = b * f - e * d;
        long yNumerator = e * c - a * f;

        if (xNumerator % denominator != 0 || yNumerator % denominator != 0) {
            return;
        }

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

        pointOfIntersection.add(new Point(x, y));
    }
}