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

문제 설명

 

프로그래머스

 

접근 방법

문제에서 나오는 그림이 주는 압박감 대비 상대적으로 해결하기 쉬웠던 문제였습니다.

 

문제에 접근했었던 방법은 단순했습니다. 일단 주어지는 직선 정보들을 통해 "교점"과 "그래프 전체 크기(가로 x 세로)"를 구한 후 그래프 상에 교점을 표기하여 이를 문자열 배열로 반환하는 것이었습니다.

 

교점을 구하는 것은 문제에서 주어지는 다음 참고사항으로 쉽게 구할 수 있었습니다.

 

 

이를 바탕으로 교점을 구하는 로직을 작성했습니다.

 

    private long[] getPoint(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 numerator = A * D - B * C;
        if (numerator == 0) {
            return null; // 두 직선은 평행 또는 일치
        }

        long denominator1 = (B * F - E * D), denominator2 = (E * C - A * F);

        if (isInteger(denominator1, numerator) && isInteger(denominator2, numerator)) {
            long x = denominator1 / numerator, y = denominator2 / numerator;
            return new long[]{x, y};
        }

        return null; // 교점이 정수가 아닌 경우
    }

 

이후에는 이렇게 구한 교점의 좌표 정보들을 바탕으로 그래프의 가로 및 세로 길이를 구하도록 했습니다.

 

List<long[]> points = new ArrayList<>();

long[] point = getPoint(line[i], line[j]);
if (point != null) {
    maxWidth = Math.max(maxWidth, point[0]);
    maxHeight = Math.max(maxHeight, point[1]);
    minWidth = Math.min(minWidth, point[0]);
    minHeight = Math.min(minHeight, point[1]);
    points.add(point);
}
                
long boardWidth = Math.abs(maxWidth - minWidth) + 1, boardHeight = Math.abs(maxHeight - minHeight) + 1;

boolean[][] board = new boolean[(int) boardHeight][(int) boardWidth];

 

이제 좌표 값을 통해 그래프 상에 교점을 표기하는 작업을 해야하는데, 이때 그래프의 요소의 인덱스는 0, 1, 2, ... 의 형태를 띄고 있으므로 각 교점들의 좌표 값에 offset을 더해줄 필요가 있습니다. 이때 offset 값은 "최초 인덱스 값 0 - 최소 좌표값"으로 구할 수 있습니다. 

 

        long widthOffset = -minWidth, heightOffset = -minHeight;
        for (long[] point : points) {
            board[(int) (point[1] + heightOffset)][(int) (point[0] + widthOffset)] = true;
        }

 

이제 그래프 상에 별을 모두 나타내었으니 이를 문자열 배열로 반환하여 응답해주기만 하면 됩니다. 이때 주의할 점으로는 앞서 x, y 좌표별로 각각 offset을 더해주었는데, y축의 좌표 같은 경우에는 가장 낮은 좌표 값(음수)부터 인덱스 0이 할당되기 때문에 당초 의도했던 것과 반전되어 그래프가 나타나게 됩니다. 그리하여 이를 역순으로 뒤집어 문자열로 변환해주었습니다.

 

        String[] result = new String[(int) boardHeight];
        for (int i = (int) boardHeight - 1, j = 0; i > -1; i--, j++) {
            StringBuilder sb = new StringBuilder();

            for (boolean b : board[i]) {
                if (b) {
                    sb.append('*');
                } else {
                    sb.append('.');
                }
            }

            result[j] = sb.toString();
        }

 

참고로 현재 코드 상 int가 아닌 long을 주로 사용하고 있는데, 이는 "10만 곱하기 10만"이라는 연산이 발생할 수도 있기 때문이었습니다.

 

전체 소스 코드

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

class Solution {

    List<long[]> points = new ArrayList<>();

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

        int size = line.length;
        long maxWidth = -10000000001l, maxHeight = -10000000001l, minWidth = 10000000001l, minHeight = 10000000001l;
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                long[] point = getPoint(line[i], line[j]);
                if (point != null) {
                    maxWidth = Math.max(maxWidth, point[0]);
                    maxHeight = Math.max(maxHeight, point[1]);
                    minWidth = Math.min(minWidth, point[0]);
                    minHeight = Math.min(minHeight, point[1]);
                    points.add(point);
                }
            }
        }

        if (points.size() == 1) {
            return new String[]{"*"};
        }

        long boardWidth = Math.abs(maxWidth - minWidth) + 1, boardHeight = Math.abs(maxHeight - minHeight) + 1;

        boolean[][] board = new boolean[(int) boardHeight][(int) boardWidth];

        long widthOffset = -minWidth, heightOffset = -minHeight;
        for (long[] point : points) {
            board[(int) (point[1] + heightOffset)][(int) (point[0] + widthOffset)] = true;
        }

        String[] result = new String[(int) boardHeight];
        for (int i = (int) boardHeight - 1, j = 0; i > -1; i--, j++) {
            StringBuilder sb = new StringBuilder();

            for (boolean b : board[i]) {
                if (b) {
                    sb.append('*');
                } else {
                    sb.append('.');
                }
            }

            result[j] = sb.toString();
        }

        return result;
    }

    private long[] getPoint(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 numerator = A * D - B * C;
        if (numerator == 0) {
            return null; // 두 직선은 평행 또는 일치
        }

        long denominator1 = (B * F - E * D), denominator2 = (E * C - A * F);

        if (isInteger(denominator1, numerator) && isInteger(denominator2, numerator)) {
            long x = denominator1 / numerator, y = denominator2 / numerator;
            return new long[]{x, y};
        }

        return null; // 교점이 정수가 아닌 경우
    }

    private boolean isInteger(double denominator, double numerator) {
        double temp = denominator / numerator;
        if (temp - (long) (denominator / numerator) == 0) {
            return true;
        }

        return false;
    }
}

 

참고자료

• https://school.programmers.co.kr/learn/courses/30/lessons/87377#qna