프로그래머스 87377: 교점에 별 만들기[JAVA]

[문제 링크]

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

프로그래머스

[난이도]

- Level 2

 

[알고리즘]

- 구현

- 배열

 

[코드]

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        long maxX = Long.MIN_VALUE;
        long maxY = Long.MIN_VALUE;
        long minX = Long.MAX_VALUE;
        long minY = Long.MAX_VALUE;

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

        for (int i = 0; i < line.length - 1; i++) {
            for (int j = i + 1; j < line.length; 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 denominator = A * D - B * C;

                if (denominator == 0) continue;  // 평행 또는 동일 직선

                long numeratorX = B * F - E * D;
                long numeratorY = E * C - A * F;

                // 정수 교차점인지 확인
                if (numeratorX % denominator != 0 || numeratorY % denominator != 0) continue;

                long x = numeratorX / denominator;
                long y = numeratorY / denominator;

                maxX = Math.max(maxX, x);
                maxY = Math.max(maxY, y);
                minX = Math.min(minX, x);
                minY = Math.min(minY, y);

                list.add(new long[]{x, y});
            }
        }

        int width = (int)(maxX - minX + 1);
        int height = (int)(maxY - minY + 1);

        char[][] graph = new char[height][width];
        for (char[] row : graph) {
            Arrays.fill(row, '.');
        }

        for (long[] point : list) {
            int x = (int)(point[0] - minX);
            int y = (int)(maxY - point[1]);  // y축 뒤집기

            graph[y][x] = '*';
        }

        String[] answer = new String[height];
        for (int i = 0; i < height; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < width; j++) {
                sb.append(graph[i][j]);
            }
            answer[i] = sb.toString();
        }

        return answer;
    }
}

 

[풀이]

단순 구현 문제이다. 중요한점은 int가 아닌 long타입으로 변환해서 풀어야한다는것이다. 그 이유는 int*int가 int의 범위를 벗어나는 경우가 있어 테스트케이스29번을 통과하지 못하기 때문이다.