프로그래머스 Level2 자바 - 교점에 별 만들기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87377?language=java 

프로그래머스

코드작성

해당 문제는 좌표를 표현해야 하므로 좌표를 나타내는 클래스를 우선 생성해 줍니다.

private static class Point{
        public final long x, y;

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

x,y 좌표는 데이터를 나타내 주므로 final을 이용해서 불변성을 갖게 하고, 해당 클래스는 생성자로 초기화 할 수있게 만들었습니다.

좌표 범위를 모르기 때문에, long을 이용해서 표현합니다.

1. 교점의 좌표 구하기

두 직선의 교점을 구하는 식

$$ a_{1}x + b_{1}y + c_{1} = 0 $$

$$ a_{2}x + b_{2}y + c_{2} = 0 $$

해당 직선의 교점은

다음과 같이 계산 할 수 있습니다

$$ x = \frac{(b_1c_2 - b_2c_1)}{(a_1b_2 - a_2b_1)} $$

$$ y = \frac{(a_2c_1 - a_1c_2)}{(a_1b_2 - a_2b_1)} $$

해당 식을 코드로 구현해 봅시다

private Point intersection(long a1, long b1, long c1, long a2, long b2, long c2){ //두 교점의 좌표 구하기
        double x = (double) (b1*c2 - b2*c1) / (a1*b2 - a2*b1);
        double y = (double) (a2*c1 - a1*c2) / (a1*b2 - a2*b1);

        if (x % 1 != 0 || y % 1 != 0) return null; // 정수만 반환 하기
        return new Point((long) x, (long) y);
    };

반환된 정수 좌표를 List형태로 저장하는 코드를 solution에 작성해줍니다.

List<Point> points = new ArrayList<>();
        for(int i = 0; i < line.length; i++) {  // i번째 직선과 교차하는 점에서 정수만 탐색
            for(int j = i+1; j < line.length; j++){
                Point intersection = intersection(line[i][0], line[i][1], line[i][2],
                        line[j][0], line[j][1], line[j][2]);
                                if(intersection != null) {
                    points.add(intersection);
                }
            };
        };

2. 저장된 정수들에 x, y의 최대, 최소값 구하기

별을 나타내기 위한 배열의 크기를 정하기 위해서 x와 y의 최대값과 최소값을 반환하는 함수를 선언합니다.

private Point getMinimumPoint(List<Point> points) { // 정수인 교점 x,y의 최소값 구하기 
        long x = Long.MAX_VALUE;
        long y = Long.MAX_VALUE;

        for (Point p : points){
            if (p.x < x) x = p.x;
            if (p.y < y) y = p.y;
        };
        return new Point(x, y);
    };

    private Point getMaximumPoint(List<Point> points){ // 정수인 교점 x,y의 최대값 구하기 
        long x = Long.MIN_VALUE;
        long y = Long.MIN_VALUE;

        for (Point p : points){
            if (p.x > x) x = p.x;
            if (p.y > y) y = p.y;
        };
        return new Point(x, y);
    }

3. 최대, 최소값 이용해서 2차원 배열 생성

구한 maximum값과 minimum 값을이용해서 solution 메서드에서 배열객체를 만들어 줍니다.

Point minimum = getMinimumPoint(points);  // 2차원 배열의 크기 결정
Point maximum = getMaximumPoint(points);
int width = (int) (maximum.x - minimum.x + 1);
int height = (int) (maximum.y - minimum.y + 1);

char[][] arr = new char[height][width]; //크기가 결정된 배열에 '.' 채워주기
    for(char[] row: arr){
        Arrays.fill(row, '.');
    };

4. 2차원 배열에 별 표시

일반 좌표와 달리 2차원 좌표는 음수(-) 좌표가 존재하지 않고, y축 좌표는 방향이 반대(아래로 내려 갈수록 값이 증가)입니다. 최대값과 최소값을 이용해서 좌표를 변환시켜 줍니다.

for (Point p : points){  //2차원 배열에는 -값 좌표가 없고, 0 부터 시작하는 값에서 최대값과 최소값과의 크기 차이를 이용해서 좌표를 결정해야 함
            int x = (int) (p.x - minimum.x);
            int y = (int) (maximum.y - p.y);
            arr[y][x] = '*';
        };

5. 문자열 배열로 변환

String[] result = new String[arr.length];
        for(int i = 0; i <result.length; i++) {
            result[i] = new String(arr[i]);
        };

전체 코드

import java.util.*;

class Solution {
    private static class Point{
        public final long x, y;

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

    private Point intersection(long a1, long b1, long c1, long a2, long b2, long c2){ //두 교점의 좌표 구하기
        double x = (double) (b1*c2 - b2*c1) / (a1*b2 - a2*b1);
        double y = (double) (a2*c1 - a1*c2) / (a1*b2 - a2*b1);

        if (x % 1 != 0 || y % 1 != 0) return null; // 정수만 반환 하기
        return new Point((long) x, (long) y);
    };

    private Point getMinimumPoint(List<Point> points) { // 정수인 교점 x,y의 최소값 구하기
        long x = Long.MAX_VALUE;
        long y = Long.MAX_VALUE;

        for (Point p : points){
            if (p.x < x) x = p.x;
            if (p.y < y) y = p.y;
        };
        return new Point(x, y);
    };

    private Point getMaximumPoint(List<Point> points){ // 정수인 교점 x,y의 최대값 구하기
        long x = Long.MIN_VALUE;
        long y = Long.MIN_VALUE;

        for (Point p : points){
            if (p.x > x) x = p.x;
            if (p.y > y) y = p.y;
        };
        return new Point(x, y);
    }

    public String[] solution(int[][] line) {
        String[] answer = {};
        List<Point> points = new ArrayList<>();
        for(int i = 0; i < line.length; i++) {  // i번째 직선과 교차하는 점에서 정수만 탐색
            for(int j=i+1; j < line.length; j++){
                Point intersection = intersection(line[i][0], line[i][1], line[i][2],
                        line[j][0], line[j][1], line[j][2]);

                if( intersection != null) {
                    points.add(intersection);
                }
            };
        };
        Point minimum = getMinimumPoint(points);  // 2차원 배열의 크기 결정
        Point maximum = getMaximumPoint(points);
        int width = (int) (maximum.x - minimum.x + 1);
        int height = (int) (maximum.y - minimum.y + 1);

        char[][] arr = new char[height][width]; //크기가 결정된 배열에 '.' 채워주기
        for(char[] row: arr){
            Arrays.fill(row, '.');
        };

        for (Point p : points){  //2차원 배열에는 -값 좌표가 없고, 0 부터 시작하는 값에서 최대값과 최소값과의 크기 차이를 이용해서 좌표를 결정해야 함
            int x = (int) (p.x - minimum.x);
            int y = (int) (maximum.y - p.y);
            arr[y][x] = '*';
        };

        String[] result = new String[arr.length];
        for(int i = 0; i <result.length; i++) {
            result[i] = new String(arr[i]);
        };

        return answer = result;

    }
}