[Algorithm]교점에 별만들기(Java)

01. 문제내용

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

프로그래머스

02. 문제풀이로 배운점

1. 범위를 잘 보고 long타입을 적절히 사용해주자(int 형의 경우 -2,147,483,648 ~ 2,147,483,647 약 20억정도 범위를 가진다.)
2. 데이터를 나타내는 클래스 일때,  final 키워드를 사용하여 불변성을 가지게 하고 생성자로 초기화할 수 있게 선언해주는 것이 좋다.
3. 상황에 맞는 자료구조를 잘 사용하자
   
   • ArrayList : 초반의 points같은 경우 삽입이 빈번하고 길이가 고정되어 있지 않아 ArrayList를 사용하여 풀이하였다.
   • Array : 마지막으로 return하는 배열의 경우 길이가 고정되어 있기 때문에 Array를 사용했다.

03. 문제 풀이법 

1. 모든 직선 쌍에 대해 반복(교점 좌표구하기, 정수 좌표 저장하기)
2. 저장된 정수들에 대해 최대 x, y 좌표의 최댓값, 최솟값 구하기
3. 구한 최댓값, 최솟값을 이용해 2차원 배열의 크기 결정
4. 2차원 배열에 별을 표시
5. 문자열 배열로 변환후 반환하기

 

04. 문제 풀이법 

1. 좌표 틀로 사용할 Point 클래스

private static class Point {
	//데이터를 나타내는 클래스 이므로 final 키워드를 사용하여 불변성을 가지게 하고, 
	//생성자로 초기화할 수 있게 선언한다.
	public final long x, y;
	private Point(long x, long y){
		this.x = x;
		this.y = y;
	}
}

2. 모든 직선에 대해 반복하기

for(int i = 0; i < line.length();i++){
	for(int j = i; j < line.length; j++ ){
	}
}

 

3. 교점 좌표구하기

private Point intersection(A, B, E, C, D, 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 new Point((long)x, (long)y);
    } else{
        return null;
    }
}

 

4. 반환된 정수 좌표 저장하기

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){
			points.add(intersection);
		}
	}
}

 

5. 지정된 정수들에 대해 x, y 좌표의 최댓값과 최솟값 구하기

private Point getMinnumPoint(List<Point> points){
	long x = Long.MAX_VALUE;
	long y = Long.MAX_VALUE;

	for(Point p: points){
		if(p.x < x) x = p.x;
		if(p.y < y) y = p.y;
	}

	return new Point(x,y);
}

private Point getMaxnumPoint(List<Point> ponints){
	long x = Long.MIN_VALUE;
	long y = Long.MIN_VALUE;

	for(Point p: points){
		if(p.x < x) x = p.x;
		if(p.y < y) y = p.y;
	}
}

 

6. 구한 최댓값 최솟값을 사용해 2차원 배열 설정하기

private Point getMinnumPoint(List<Point> points){
	long x = Long.MAX_VALUE;
	long y = Long.MAX_VALUE;

	for(Point p: points){
		if(p.x < x) x = p.x;
		if(p.y < y) y = p.y;
	}

	return new Point(x,y);
}

private Point getMaxnumPoint(List<Point> ponints){
	long x = Long.MIN_VALUE;
	long y = Long.MIN_VALUE;

	for(Point p: points){
		if(p.x < x) x = p.x;
		if(p.y < y) y = p.y;
	}
}

 

7. 2차원 배열에 '.'을 채워 초기화하기

char[][] arr = new char[height][width];
for(char[]row : arr){
	Arrays.fill(row, '.');
}

 

8. 2차원에 배열에 교점 표시하기

for(Point p: points){
	int x = (int)(p.x - minnum.x);
	int y = (int)(maxnum.y - p.y);
	arr[y][x] = '*';
}

 

9. 문자열을 배열로 변환한 후 반환하기!

String[] result = new String[arr.length];

for(int i = 0; i < result.length; i++){
	result[i] = new String(arr[i]);
}
return result;

 

 

---

10. 최종 풀이법

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

class Solution {
    
    private static class Point{
        public final long x;
        public final long y;
        
        private Point(long x, long y){
            this.x = x;
            this.y = y;
        }
    }
    
    
    //교차점 구해서 정수인 교차점만 반환하기
    public 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){
            // System.out.println( "x : " + x);
            // System.out.println("(" + (long)x + ", " + (long)y + ")");
            return new Point((long)x, (long)y);
        } else{
            return null;
        }
    }
    
    public Point getMaxNum(List<Point> points){
        long x = Long.MIN_VALUE;
        long y = Long.MIN_VALUE;
        
        for (Point p : points){
            if(p.x > x) x = p.x;
            if(p.y > y) y = p.y;
        }
        
        return new Point(x, y);
    }
    
    public Point getMinNum(List<Point> points){
        long x = Long.MAX_VALUE;
        long y = Long.MAX_VALUE;
        
        
        for (Point p : points){
            if(p.x < x) x = p.x;
            if(p.y < y) y = p.y;
        }
        
        return new Point(x, y);
        
    }
    
    public String[] solution(int[][] line) {
        String[] answer = {};
        
        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) points.add(intersection);
            }
        }
        
        
        Point minNum = getMinNum(points);
        Point maxNum = getMaxNum(points);
        
//         System.out.println(minNum.x);
//         System.out.println(minNum.y);
        
//         System.out.println(maxNum.x);
//         System.out.println(maxNum.y);
        
        int width = (int)(maxNum.x - minNum.x + 1);
        int height = (int)(maxNum.y - minNum.y + 1);
        
        
        //별로 출력해보기 
        char[][] arr = new char[height][width];
        for(char[] row : arr){
            Arrays.fill(row, '.');
        }
        
        //교차 지점에 별 넣어주기 
        for(int i = 0; i < points.size(); i++){
            int x = (int)points.get(i).x;
            int y = (int)points.get(i).y;
            
            int testx = x - (int)minNum.x;
            int testy = (int)maxNum.y - y;
            
            arr[testy][testx] = '*';
            System.out.println("(" + x + ", " + y + ")");
            System.out.println("(" + testx + ", " + testy + ")");
            
        }
        
        String[] result = new String[arr.length];
        
        for(int i = 0; i < result.length; i++){
            result[i] = new String(arr[i]); 
        }
        
        
        return result;
    }
    
    
}

 

문제 출처 : 프로그래머스(https://school.programmers.co.kr/learn/courses/30/lessons/87377)