카테고리: 배열

문제

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

풀이 방식

1.모든 직선 쌍에 대한 반복을 수행한다.

for(int y1 = 0; y1 < line.length; y1++){
	for(int y2 = y1+1; y2 < line.length; y2++){
    	
    }
 }

2.정수 교점을 찾는다.

private static Point searchPoint(long a, long b, long e, long c, long d, long f){
	//정수 교점만
    if((b*f-e*d) % (double)(a*d-b*c) == 0 && (e*c-a*f) % (double)(a*d-b*c) == 0){
    	long x = (b*f-e*d) / (a*d-b*c);
        long y = (e*c-a*f) / (a*d-b*c);

		return new Point(x,y);
    }

	return null;
}

3.별 그릴 최소 크기의 격자판 2차원 배열 만들기

//배열의 크기먼저. x의 최소값과 최대값 차이가 열이되고, y의 최댓값 최솟값 차이가 행의 크기가 됨
Point min_point = getMinPoint(points);
Point max_point = getMaxPoint(points);

//최소 행열 구하기
int height = (int)(max_point.y - min_point.y +1);//몇행
int width = (int)(max_point.x - min_point.x +1);//몇열

char[][] paint = new char[height][width];

4.격자판에 *그릴 좌표 새로 구하기

for(Point point : points){
	int x = (int)(point.x - min_point.x);
    int y = (int)(max_point.y - point.y);

	paint[y][x] = '*';
}

최종 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    private static class Point{
        public final long x,y;
        private Point(long x, long y){
            this.x = x;
            this.y = y;
        }
    }

    private static Point searchPoint(long a, long b, long e, long c, long d, long f){
        //정수 교점만
        if((b*f-e*d) % (double)(a*d-b*c) == 0 && (e*c-a*f) % (double)(a*d-b*c) == 0){
            long x = (b*f-e*d) / (a*d-b*c);
            long y = (e*c-a*f) / (a*d-b*c);

            return new Point(x,y);
        }

        return null;
    }

    private static Point getMinPoint(List<Point> points){
        long min_x = Long.MAX_VALUE;
        long min_y = Long.MAX_VALUE;

        for(Point point : points){
            if(point.x < min_x) min_x = point.x;
            if(point.y < min_y) min_y = point.y;
        }

        return new Point(min_x, min_y);
    }

    private static Point getMaxPoint(List<Point> points){
        long max_x = Long.MIN_VALUE;
        long max_y = Long.MIN_VALUE;

        for(Point point : points){
            if(point.x > max_x) max_x = point.x;
            if(point.y > max_y) max_y = point.y;
        }

        return new Point(max_x, max_y);

    }

    public String[] solution(int[][] line){
        List<Point> points = new ArrayList<>();

        //1. 모든 직선 쌍에 대한 반복
        for(int y1 = 0; y1 < line.length; y1++){
            for(int y2 = y1+1; y2 < line.length; y2++){
                // 2. 교점 구하기
                Point intersection = searchPoint(line[y1][0], line[y1][1], line[y1][2], line[y2][0], line[y2][1], line[y2][2]);
                if(intersection != null){
                    points.add(intersection);
                }
            }
        }

        //3. 별 그릴 최소 크기의 격자판 2차원 배열 만들기
        //배열의 크기먼저. x의 최소값과 최대값 차이가 열이되고, y의 최댓값 최솟값 차이가 행의 크기가 됨
        Point min_point = getMinPoint(points);
        Point max_point = getMaxPoint(points);

        //최소 행열 구하기
        int height = (int)(max_point.y - min_point.y +1);//몇행
        int width = (int)(max_point.x - min_point.x +1);//몇열

        //격자판 만들기
        char[][] paint = new char[height][width];
        for(char[] row : paint){
            Arrays.fill(row, '.');
        }

        //4. 격자판 별 그리기
        for(Point point : points){
            int x = (int)(point.x - min_point.x);
            int y = (int)(max_point.y - point.y);

            paint[y][x] = '*';
        }

        //String 1차원 배열로 변환
        String[] result = new String[paint.length];
        for(int i=0; i < paint.length; i++){
            result[i] = new String(paint[i]);
        }

        return result;
    }
}