[프로그래머스] 위클리 10주차 - 교점에 별 만들기 JAVA

[문제링크]

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

코딩테스트 연습 - 10주차_교점에 별 만들기

 

[문제]

직선의 교점 중 X, Y 좌표가 모두 정수인 교점만 골라서

상대좌표 형식으로 만든 다음에 * 찍어서 출력하세요.

 

[풀이]

1. 직선의 교점을 모두 구한다. (친절하게 문제 말미에 어떻게 하면 직선의 교점을 구할 수 있는지 공식이 주어진다.)

2. 직선의 교점이 정수인지 확인하고 정수면 리스트에 등록한다.

3. 직선의 교점이 정수인지 확인하는 중간에 나중에 상대좌표로 만들때 용이하게끔 maxX좌표, maxY좌표, minX좌표, minY좌표를 구해놓는다.

4. 리스트에 등록되있는 좌표들을 하나씩 꺼내서 해당 좌표에 minX 좌표, minY 좌표를 빼준다. 즉, 상대좌표로 만든다.

5. 미리 minX, maxX 를 이용해 만들어 놓은 2차원 배열에서 상대좌표로 만든 좌표에 해당 하는 곳에 별을 찍는다.

6. 최종적으로 String 배열 형태로 반환해야 하기때문에 2차원 배열을 String배열로 변환해준다.

 

[함정] 

minX, maxX 를 구하려면 미리 MAX 값을 선정해서 상단에 선언해놓아햐 합니다. 

그런데 이걸 처음에 평소처럼 987654321 이라고 하면 런타임 에러가 납니다. 왜냐하면 교점이 AD-BC 가 INT범위를 넘어가는 경우가 생기기 때문입니다. 그래서 앞에 1을 한개씩 붙여가면서 돌려본 결과, 11987654321L 로 지정하니 통과했습니다. 

 

[소스 코드]

import java.util.*;
class Solution {
    class Point{
        long x, y;
        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }
  
    public String[] solution(int[][] line) {
        long minX=11987654321L;
        long minY=11984654321L;
        long maxX=-11984654321L;
        long maxY=-11984654321L;
        
        // 교점 모음 리스트
        ArrayList<Point> arr = new ArrayList<>();
        
        for (int i=0; i<line.length-1; i++) {
            for (int j=i+1; j<line.length; j++) {
                long a=line[i][0];
                long b=line[i][1];
                long e=line[i][2];
                long c=line[j][0];
                long d=line[j][1];
                long f=line[j][2];
                long x_under = a*d - b*c;
                if(x_under == 0) continue; // 두 직선이 평행하다.
                
                long x_upper = b*f - e*d; 
                long y_upper = e*c - a*f;
                if(x_upper % x_under == 0 && y_upper % x_under ==0){
                    long x = x_upper/x_under; //열
                    long y = y_upper/x_under; //행
                    
                    arr.add(new Point(x,y));
                    if(x<minX) minX=x;
                    if(x>maxX) maxX=x;
                    if(y<minY) minY=y;
                    if(y>maxY) maxY=y;
                } 
            }
        }
        
        int ysize= (int)(maxY-minY+1);
        int xsize= (int)(maxX-minX+1);
        String[][] answer = new String[ysize][xsize];
        String[] ans = new String[ysize];
    
    	// 상대좌표로 변경
        for (Point p : arr) {
            int a= (int)(p.x-minX);
            int b= (int)(p.y-minY);
            answer[b][a]="*"; 
        }
    
    	// 정답형태로 변환
        for (int i=0; i<answer.length; i++){
            String line1="";
            for (int j=0; j<answer[i].length; j++){
                if(answer[i][j] == null) line1+=".";
                else line1+=answer[i][j];
            }
            ans[answer.length-1-i] = line1;
        }
        return ans;
    }
}