교점에 별 만들기(위클리 챌린지 )

문제

코드

import java.util.*;

class Solution {
    class Coordinate{
        long x;
        long y;
        Coordinate(long x,long y){
            this.x=x;
            this.y=y;
        }
    }
    public String[] solution(int[][] line) {
        String[] answer;
        ArrayList<Coordinate> coordinate=new ArrayList<>();
        long minX=Long.MAX_VALUE;
        long minY=Long.MAX_VALUE;
        long maxX=Long.MIN_VALUE;
        long maxY=Long.MIN_VALUE;
        
        for(int i=0;i<line.length;i++){
            for(int j=i+1;j<line.length;j++){
                long adbc=((long)line[i][0]*(long)line[j][1])-((long)line[i][1]*(long)line[j][0]);
                if(adbc==0) continue;
                double x=(((long)line[i][1]*(long)line[j][2])-((long)line[i][2]*(long)line[j][1]))/(double)adbc;
                double y=(((long)line[i][2]*(long)line[j][0])-((long)line[i][0]*(long)line[j][2]))/(double)adbc;
                if(x-(long)x==0&&y-(long)y==0){
                    coordinate.add(new Coordinate((long)x,(long)y));
                    minX=Math.min(minX,(long)x);    
                    minY=Math.min(minY,(long)y);
                    maxX=Math.max(maxX,(long)x);
                    maxY=Math.max(maxY,(long)y);
                }
            }
        }
        long sizeX=maxX-minX+1;
        long sizeY=maxY-minY+1;
        
        answer=new String[(int)sizeY];
        boolean star[][]=new boolean[(int)sizeY][(int)sizeX];
        for(Coordinate c:coordinate)
            star[(int)(maxY-c.y)][(int)(c.x-minX)]=true;
        
        for(int i=0;i<(int)sizeY;i++){
            StringBuilder s=new StringBuilder();
            for(int j=0;j<(int)sizeX;j++){
                if(star[i][j]==true)
                    s.append("*");
                else
                    s.append(".");
            }
            answer[i]=s.toString();
        }
        return answer;
    }
}

풀이

(1) 교점의 좌표를 저장할 Coordinate 클래스를 만들어 준다. 생성자와 멤버변수 x,y를 갖는다.
(2) 문제에서 주어진 식을 이용해, 모든 식 간의 교점을 구해준다.
(3) 그 교점이 정수인지 판단 후 x,y 좌표가 둘다 정수라면, Coordinate형 ArrayList에 추가해준다. 이 때 게속해서 x,y좌표의 최소,최대 점을 갱신해주어야 한다(별을 찍을 때 최소 사각형을 만들어 주어야 함이다)
(4) 위 과정이 끝나면, 교점의 x,y좌표 최대점 최소점을 통해 최소 사각형 사이즈를 구한다. 그리고 그 크기의 boolean형 이차원 배열을 만들어 준다. ArrayList에 있는 교점들의 좌표를 적절히 옮겨(배열 의 인덱스는 0부터 시작하기 때문이다), 그 좌표를 boolean형 배열에 true로 만들어준다.
(5) boolean형 배열을 순회하며, false인곳은 ".", true인 곳은 "*"을 찍어준다.

결과

교점을 구하는 식을 문제에서 주었고, 특별한 알고리즘을 요구하지 않는 문제였다. 교점의 좌표들을 최소 사각형으로 만들고, String형 배열로 잘 만들어 주는 것이 살짝 어렵긴 했다. 그리고, 테스트를 돌릴 때 데이터 타입때문에 계속 통과를 못했다. 모든 변수들을 long형으로 다루어 주어야 했다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges