[프로그래머스] 교점에 별 만들기 (Java)

프로그래머스

접근 방식

주어지는 방정식들의 모든 교점을 구하고 교점에 별을 찍어 출력하면 되는 문제이다. 문제에서 교점이 무수히 많이 발생하거나(일치하는 경우)는 없다고 가정했기 때문에 모든 경우에 수에 대해 문제 하단에 있는 교점 구하는 공식을 이용하여 교점을 구하면 된다. 격자판은 최소 크기로 그려야 하므로 교점이 찍히는 위치들의 최소값, 최대값을 구하고 그 좌표들을 기준으로 격자판의 폭과 높이를 산출할 수 있다. 좌표정보를 저장하기 위한 클래스 Coordinate을 생성하여 좌표리스트, 좌표 최소/최대값, 격자판 크기 산출에 활용하였다.

로직 설명

- 좌표정보를 저장할클래스 Coordinate 생성 (생성자 및 setter 포함)

- 교점들이 저장될 Coordinate 리스트 cList 생성

- (교점 저장하기) line 배열을 이중반복문으로 돌려 모든 조합을 탐색하며:

1) 공식의 a, b, c, d, e, f 에 해당하는 숫자 할당

2) a*d - b*c 가 0이 아니면 정수여부 점검 후 cList에 좌표 정보 삽입

- cList를 탐색하며 최대값, 최소값 좌표 구한 후 격자판의 너비와 높이 산출

- 격자판에 교점 찍기 (교점 찍을 때 부호 바뀌는 것 주의)

- 한 행씩 문자열로 변환하여 답변 배열에 추가

Note

- 2차원 배열 선언 시 y값이 먼저 오고, x값이 나중에 온다는 사실을 잊지 말자.

정답코드 

import java.util.*;
//좌표 클래스
class Coordinate {
    long x;
    long y;
    
    Coordinate(long x, long y){
        this.x = x;
        this.y = y;
    }
    
    void setX(long x){
        this.x = x;
    }
    
    void setY(long y){
        this.y = y;
    }
}

class Solution {
    public String[] solution(int[][] line) {
        //교점을 저장할 좌표 리스트
        List<Coordinate> cList = 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], b = line[i][1], e = line[i][2],
                     c = line[j][0], d = line[j][1], f = line[j][2];
                
                if((a * d - b * c) != 0){
                    double x = (double) (b * f - e * d) / (a * d - b * c);
                    double y = (double) (e * c - a * f) / (a * d - b * c);
                    if(x % 1 == 0 && y % 1 == 0){                           //정수인 경우에만 저장
                        cList.add(new Coordinate((long)x, (long)y));   
                    }
                }
            }
        }
        //교점의 최소, 최대값 찾기
        Coordinate min = new Coordinate(Long.MAX_VALUE, Long.MAX_VALUE);
        Coordinate max = new Coordinate(Long.MIN_VALUE, Long.MIN_VALUE);
        
        for(Coordinate c : cList){
            long cx = c.x, cy = c.y;
            
            if(cx < min.x){
                min.setX(cx);
            }
            
            if(cy < min.y){
                min.setY(cy);
            }
            
            if(cx > max.x){
                max.setX(cx);
            }
            
            if(cy > max.y){
                max.setY(cy);
            }
        }
        
        //격자판 크기 산출 후 격자판 배열 선언
        int width = (int)(max.x - min.x + 1);
        int height = (int)(max.y - min.y + 1);
            
        char[][] arr = new char[height][width];
        
        for(int i = 0; i < height; i++){
            for(int j = 0; j < width; j++){
                arr[i][j] = '.';
            }           
        }
        //교점 찍기
        for(Coordinate c : cList){
            arr[(int)(max.y - c.y)][(int)(c.x - min.x)] = '*';
        }
        //답변배열 생성 후 격자판 문자열로 변환하여 저장
        String[] answer = new String[height];
        for(int i = 0; i < answer.length; i++){
            answer[i] = new String(arr[i]);
        }
        
        return answer;
    }
}