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

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

1. 문제 설명

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)입니다.

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

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

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

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

따라서 정답은 

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

입니다.

직선 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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

---

입출력 예lineresult

[[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]]	["*"]

---

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

직선 y = 1, x = 1, x = -1는 다음과 같습니다.

(-1, 1), (1, 1) 에서 교점이 발생합니다.

따라서 정답은 

"*.*"  

입니다.

입출력 예 #3

직선 y = x, y = 2x는 다음과 같습니다.

(0, 0) 에서 교점이 발생합니다.

따라서 정답은 

"*"  

입니다.

입출력 예 #4

직선 y = x, y = 2x, y = 4x는 다음과 같습니다.

(0, 0) 에서 교점이 발생합니다.

따라서 정답은 

"*"

입니다.

---

참고 사항

Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.

 

2. 풀이 방법

1. 2중 반복문을 이용하여 교점을 구해준다.

 

 

** 정수인지 실수인지 판별하는 법!

double 형식의 x가 있다면 1로 나머지 연산을 해본다. 만약 답이 0이면 정수, 0이 아니라면 실수이다.

 

2. 교점의 x, y 최대 최소를 구해준다. -> 최소한의 좌표 평면을 이용해야하기 때문

 

3. x, y 최대 최소를 이용해 2차원 문자 배열의 크기를 결정해주고 전부 '.'으로 채워준다.

** 좌표 평면은 음수 좌표가 없기 때문에 (x_max - x_min + 1)을 이용해 양수로 바꿔주었으며 y좌표로 먼저 접근한 후에 x좌표로 접근해야 했다.

 

4. 교점의 좌표에는 '*' 채워준다.

 

 

** 실제 좌표의 범위가 나타나있지 않아 좌표를 모두 long 형식으로 받아주었다. 이렇게 하지 않으면 마지막 테스트케이스에서 틀렸다고 나온다 ㅠㅠ

3. 전체 코드

 

import java.util.ArrayList;

class Solution {
    public String[] solution(int[][] line) {
        double x;
        double y;
        long x_max = 0;
        long x_min = 0;
        long y_max = 0;
        long y_min = 0;
        String[] answer;

        // 2중 반복문을 이용해 교점 구하기
        for (int i = 0; i < line.length; i++) {
            for (int j = i + 1; j < line.length; j++) {
                x = (double) ((long) line[i][1] * (long) line[j][2] - (long) line[i][2] * (long) line[j][1]) / ((long) line[i][0] * (long) line[j][1] - (long) line[i][1] * (long) line[j][0]);
                y = (double) ((long) line[i][2] * (long) line[j][0] - (long) line[i][0] * (long) line[j][2]) / ((long) line[i][0] * (long) line[j][1] - (long) line[i][1] * (long) line[j][0]);

                // 만약 정수가 아니라면 건너뜀
                if (x % 1 != 0)
                    continue;
                if (y % 1 != 0)
                    continue;

                // 정수라면 pointList에 add해준다.
                Point p = new Point((long) x, (long) y);
                Point.pointList.add(p);
            }
        }


        // x,y의 최대 최소가 들어있는 배열
        long[] arrayMaxMin = Point.getMaxMin(Point.pointList);
        x_max = arrayMaxMin[0];
        x_min = arrayMaxMin[1];
        y_max = arrayMaxMin[2];
        y_min = arrayMaxMin[3];

        // 최대 최소를 이용해 너비와 높이를 계산한다.
        int width = (int)Point.getWidth(x_max, x_min) + 1;
        int height =(int)Point.getHeight(y_max, y_min) + 1;


        // 2차원 문자열 생성, 높이와 너비에 맞게 모두 .을 넣어준다.
        char[][] charArray = new char[height][];
        for (int i = 0; i < height; i++)
            charArray[i] = new char[width];

        for (int i = 0; i < charArray.length; i++) {
            for (int j = 0; j < charArray[0].length; j++) {
                charArray[i][j] = '.';
            }
        }

        // 해당 교점에 '.' 대신 '*'을 넣어준다.
        // 그리고 일반 좌표계와 2차원 배열은 y축 방향도 반대고 음수 죄표가 없어서 처리해준다.
        for (int i = 0; i < Point.pointList.size(); i++) {
            long y1 = Point.pointList.get(i).x - x_min; // 최솟값을 빼주어 양수로 만들어주고 x와 y를 바꾸어준다.(먼저 y좌표로 접근해야함)
            long x1 = Point.pointList.get(i).y - y_min;

            charArray[(int)x1][(int)y1] = '*';
        }


        // 정답을 넣어줄 String 배열에 char array를 String으로 변환한다.
        // 그리고 거꾸로 넣어준다
        answer = new String[(int)height];
        for (int i = 0; i < answer.length; i++) {
            answer[answer.length - i - 1] = new String(charArray[i]);
        }

        return answer;


    }
}

class Point {

    static ArrayList<Point> pointList = new ArrayList<>();
    long x;
    long y;

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

    static long[] getMaxMin(ArrayList<Point> pointList) {
        long x_max = pointList.get(0).x;
        long y_max = pointList.get(0).y;
        long x_min = pointList.get(0).x;
        long y_min = pointList.get(0).y;


        for (Point point : pointList) {
            if (point.x > x_max)
                x_max = point.x;
            if (point.x < x_min)
                x_min = point.x;
            if (point.y > y_max)
                y_max = point.y;
            if (point.y < y_min)
                y_min = point.y;
        }

        long[] arrayMaxMin = new long[4];
        arrayMaxMin[0] = x_max;
        arrayMaxMin[1] = x_min;
        arrayMaxMin[2] = y_max;
        arrayMaxMin[3] = y_min;

        return arrayMaxMin;
    }

    static long getWidth(long max, long min) {
        return max - min;
    }

    static long getHeight(long max, long min) {
        return max - min;
    }
}

 

 

---

후기

다른건 괜찮았는데 좌표 평면의 좌표대로 2차원 배열이 생성되는 것이 아니라 조금 생각하기가 어려웠다.

또한 자바에서 Char array를 String으로 변환하는 법도 알게 되었다.

(String을 생성할 때 매개변수로 Char array를 넣어주면 된다.)