프로그래머스_교점에 별 만들기(JAVA)

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

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

문제 설명

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

---

입출력 예

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

---

입출력 예 설명

입출력 예 #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인 경우 두 직선은 평행 또는 일치합니다.

---

[문제 풀이]

좌표의 곱셈 과정에서 INT 범위를 벗어나는 값이 올 경우 계산이 정확하게 되지 않는다. 따라서 곱셈을 위해 좌표를 Long으로 변환하여 계산해야 한다.

1. 중복을 제거하기 위해 hastset에 교점을 저장할 것이다.
2. 교점은 Node 클래스를 이용하여 long x, long y 값으로 이루어져 있다.
3. 교점을 구하는 식은 Ax + By +E = 0, Cx + Dy + F =0이 두 직선이라고 할 때,
   1. x = (B*F-E*D) / (A*D-B*C)
   2. y = (E*C-A*F) / (A*D-B*C)
4. 3에 의해
   1. 각 a, b, c, d, e, f는 모두 long a = A, long b = B ... 으로 선언하여 주고,
   2. x를 구하기 위한 분자, long n1 = (b*f-e*d);
   3. y를 구하기 위한 분자, long n2 = (e*c-a*f);
   4. 분모, long d1 = (a*d-b*c);
5. 정수 교점이 존재하지 않는 경우는 3가지가 존재한다.
   1. 만약 d1 ==0 이라면 두 직선은 평행하거나 같은 직선이므로 교점이 존재할 수 없다. 
   2. n1%d1 !=0 이면 정수가 아님
   3. n2%d1 !=0 이면 정수가 아님
6. 5에 해당하는 경우를 제외하고 교점을 구한다.
   1. 교점 x좌표 : long xx = n1/d1;
   2. 교점 y좌표: long yy = n2/d1;
7. 구한 교점을 set에 넣어준다. hashset은 중복을 허용하지 않으므로 자동으로 같은 좌표는 하나만 들어가게 된다.
8. 별을 찍을 좌표의 범위를 구하기 위해 min_x, min_y, max_x, max_y 값을 구한다.
9. 모든 교점을 구하고 나서 answer 배열의 크기를 할당해주어야 하는데, 이때 answer 배열의 크기는 (max_y - min_y _+1)과 같다.
10. 또한 각 answer 배열에 들어갈 string의 길이는 (max_x - min_x + 1)과 같다. 따라서 모든 배열의 값을 '.'이 (max_x - min_x + 1)개 존재하는 string으로 초기화한다.
11. hashset에 존재하는 좌표에 해당하는 '.'을 '*'로 바꾸어주어야 한다.
    1. answer[i]의 string을 stringbuilder로 바꾸어 해당 위치의 '.'을 replace를 이용하여 '*'로 바꾸어 줄 것이다.
    2. y값이 가장 큰 좌표가 answer배열의 가장 작은 인덱스에 해당하는 곳에 들어가야 한다. 따라서  StringBuilder sb = new StringBuilder(answer[(int)(answer.length-1) - (int)(n.y+dy)]); 이다.
    3. sb.replace(시작 index, 종료 index+1, 대체 string) 형식으로 사용해야하므로 answer[(int)(answer.length-1) - (int)(n.y+dy)] = sb.replace((int)n.x+(int)dx,(int)n.x+(int)dx+1, "*").toString();

[코드]

import java.util.*;
class Node{
    long x;
    long y;
    public Node(long x, long y){
        this.x = x;
        this.y = y;
    }
}
class Solution {
    public String[] solution(int[][] line) {
        String[] answer = {};
        HashSet<Node> set = new HashSet<>();
        long min_x=Long.MAX_VALUE, min_y=Long.MAX_VALUE, max_x=Long.MIN_VALUE, max_y=Long.MIN_VALUE;
        for(int i=0;i<line.length-1;i++){
            long a = line[i][0];
            long b = line[i][1];
            long e = line[i][2];
            for(int j=1;j<line.length;j++){
                long c = line[j][0];
                long d = line[j][1];
                long f = line[j][2];
                
                long n1 = b*f-e*d;
                long n2 = e*c-a*f;
                long d1 = a*d-b*c;
                
                if(d1==0 || n1%d1!=0 || n2%d1!=0)
                    continue;
                
                long xx = n1/d1;
                long yy = n2/d1;
                set.add(new Node(xx,yy));
                min_x = Math.min(min_x, xx);
                min_y = Math.min(min_y, yy);
                max_x = Math.max(max_x, xx);
                max_y = Math.max(max_y, yy);
             
                
                
            }
        }
       
       
        
        long len = max_x - min_x + 1;
        long dx = 0 - min_x; 
        long dy = 0 - min_y;
        answer = new String[(int)max_y-(int)min_y+1];
        

        for(int i=0;i<answer.length;i++){
            String s = "";
            for(int j=0;j<len;j++){
                s+=".";
            }
            answer[i] = s;
        }
        for(Node n : set){

            StringBuilder sb = new StringBuilder(answer[(int)(answer.length-1) - (int)(n.y+dy)]);

            answer[(int)(answer.length-1) - (int)(n.y+dy)] = sb.replace((int)n.x+(int)dx,(int)n.x+(int)dx+1, "*").toString();
        }





        return answer;
    }
}