[프로그래머스] Lv.2 교점에 별 만들기

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

프로그래머스

 

문제 풀이 접근

1. x,y 좌표를 저장하는 Point 클래스 생성

2. 2차원 배열의 line을 돌면서 교점 좌표를 구하여 리스트에 저장

3. x, y좌표의 최대값과 최소값을 구한다.

4. 별을 저장하는 배열의 크기는 (최대 - 최소 + 1)이 된다.

5. 2차원 배열에 점을 찍는다.

6. 교점 좌표에 별을 찍는다.

 

주의 사항
1. x,y값을 long 타입으로 지정해야 한다.
2. 정수 좌표만 계산해야 한다.
3. 2차원 배열의 크기는 [y][x] 형태가 된다.
4. 2차원 배열과 1사분면의 구조가 다르기 때문에 x = p.x - minX, y = maxY - p.y 형태로 변환해야 한다.

 

import java.util.*;
class Point {
    public long x;
    public long y;
    Point(long x, long y) {
        this.x = x;
        this.y = y;
    }
}
class Solution {
    private Point intersection(long a, long b, long e, long c, long d, long f) {
        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) return null; // 정수일때만 체크
        
        return new Point((long) x, (long) y);
    }
    
    private Point getMinimumPoint(List<Point> list) {
        long x = Long.MAX_VALUE;
        long y = Long.MAX_VALUE;
        for(Point p : list) {
            if (p.x < x) x = p.x;
            if (p.y < y) y = p.y;
        }
        return new Point(x, y);
    }
    
    private Point getMaximumPoint(List<Point> list) {
        long x = Long.MIN_VALUE;
        long y = Long.MIN_VALUE;
        for(Point p : list) {
            if (p.x > x) x = p.x;
            if (p.y > y) y = p.y;
        }
        return new Point(x, y);
    }
    
    private char[][] createBoard (Point maxP, Point minP) {
        int x = (int) (maxP.x - minP.x + 1);
        int y = (int) (maxP.y - minP.y + 1);
        
        char [][] board = new char[y][x];
        for(char [] line : board) {
            Arrays.fill(line, '.');
        }
        
        return board;
    }
    
    
    public String[] solution(int[][] line) {        
        List<Point> points = new ArrayList<>();
        for(int i = 0; i < line.length; i++){
            for(int j = i+1; j < line.length; j++) {
                Point intersection = intersection(line[i][0], line[i][1], line[i][2], line[j][0], line[j][1], line[j][2]);
                if (intersection == null) {
                    continue;
                }
                points.add(intersection);
            }
        }
        Point maxPoint = getMaximumPoint(points);
        Point minPoint = getMinimumPoint(points);
        
        char [][] board = createBoard(maxPoint, minPoint);
       
        
        for(Point p : points) {
            int x = (int) (p.x - minPoint.x);
            int y = (int) (maxPoint.y - p.y);
            board[y][x] = '*';
        }
        
        String[] answer = new String[board.length];
        for(int i = 0; i < answer.length; i++){
            answer[i] = String.valueOf(board[i]);
        }
        return answer;
    }
}

 

문제 회고

책 1번부터 어려운 문제가 나와서 많이 당황했는데, 책에서 주어진대로 하나씩 차근차근 풀어나가다 보니 생각보다 어렵지 않았다.

 

2차원 좌표가 주어질 때, Point class를 생성하는 것에 대한 중요성을 느꼈고, 2차원 좌표 -> 1사분면으로 좌표를 변환 하는 과정이 좀 까다로웠다.