[프로그래머스] 위클리챌린지 87377 교점에 별 만들기

문제

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

풀이

parameter
직선 A, B, C에 대한 정보가 담긴 배열 line
3 x 2~1000
[[A, B, C], [A, B, C], ...]

return
모든 별을 포함하는 최소 사각형

example
[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]

pseudocode
Ax + By + E = 0
Cx + Dy + F = 0
x = (BF - ED) / (AD - BC)
y = (EC - AF) / (AD - BC)

x, y 각 최소/최댓값 초기화

중복되는 교점이 존재할 수 있으므로 위치를 저장할 때 set 자료구조 이용
Set<String> set = new HashSet<>();

for(int i=0; i<line.length-1; i++){ 방정식1
    for(int j=i+1; j<line.length; j++){ 방정식2
        int 값1 = (BF - ED)
        int 값2 = (EC - AF)
        int 값3 = (AD - BC)
        
        if(값3 == 0 || 값1 % 값3 !=0 || 값2 % 값3 != 0)
            조건에 부합하지 않으므로 continue
        
        조건에 부합한 경우
        int x = 값1 / 값3
        int y = 값2 / 값3
        set.add(x+","+y)
        각 x,y에 대한 최소, 최대값 갱신
    }
}

답 배열 String answer = new String[y최대-y최소+1]
answer 의 index는 0으로 초기화

x,y 좌표를 돌면서 *와 .을 표현할 때
왼쪽 위부터 오른쪽 아래로 돈다.
이때 y값은 최댓값부터, x는 최솟값부터 돌아야 한다.

for(int j = y최댓값; j >= y최솟값; j--){
    StringBuilder sb;
    for(int i=x최솟값; i<=x최댓값; i++){
        if(set.contains(i+","+j)){
            //만약 교점 좌표라면
            sb.append("*")
        }else
            교점이 아니라면
            sb.append(".")
    }
    answer[index++] = sb.toString;
}

예외처리)
AD - BC == 0 이면 두 직선이 일치하거나 평행함
(EC - AF) / (AD - BC), (BF - EC) / (AD - BC) 값이 정수가 아니라면 문제 조건에 맞지 않음
따라서 (EC - AF) % (AD - BC) != 0 일 경우 예외처리

코드

import java.util.Set;
import java.util.HashSet;

class Solution {
    public String[] solution(int[][] line) {
        
        int maxX = Integer.MIN_VALUE;
        int maxY = Integer.MIN_VALUE;
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        
        // 좌표를 담을 set
        Set<String> set = new HashSet<>();
        
        for(int i=0; i<line.length-1; i++){
            for(int j=i+1; j<line.length; j++){
                /**
                    Ax + By + E = 0
                    Cx + Dy + F = 0
                    x = (BF - ED) / (AD - BC)
                    y = (EC - AF) / (AD - BC)
                **/
                
                // int -> long 형변환
                long A = (long) line[i][0];
                long B = (long) line[i][1];
                long C = (long) line[j][0];
                long D = (long) line[j][1];
                long E = (long) line[i][2];
                long F = (long) line[j][2];
                
                long tmp1 = B*F - E*D; //BF-ED
                long tmp2 = E*C - A*F; //EC-AF
                long tmp3 = A*D - B*C; //AD-BC
                
                // 문제 조건에 맞지 않은 경우
                if(tmp3 == 0 || tmp1 % tmp3 != 0 || tmp2 % tmp3 != 0){
                    continue;
                }
                
                // 문제 조건에 맞는 경우
                int x = (int) (tmp1 / tmp3);
                int y = (int) (tmp2 / tmp3);
                
                set.add(x+","+y);
                maxX = Math.max(maxX, x);
                maxY = Math.max(maxY, y);
                minX = Math.min(minX, x);
                minY = Math.min(minY, y);
            }
        }
        
        // 정답 배열
        String[] answer = new String[maxY - minY + 1];
        int index = 0;
        
        StringBuilder sb;
        for(int j=maxY; j>=minY; j--){
            sb = new StringBuilder();
            for(int i=minX; i<=maxX; i++){
                if(set.contains(i+","+j)){
                    sb.append("*");
                } else{
                    sb.append(".");
                }
            }
            
            answer[index++] = sb.toString();
        }
        
        return answer;
    }
}