프로그래머스 - 교점에 별만들기

leehyunjon·2022년 9월 6일

구현 프로그래머스

Algorithm

목록 보기

111/162

교점에 별 만들기 : https://school.programmers.co.kr/learn/courses/30/lessons/87377

Problem

Solve

각 직선에서의 교차점을 찾기 위해서 x와 y를 찾는것이 핵심이라 생각합니다.

비교할 두 직선이 Ax+By+E=0, Cx+Dy+F=0 이라 할때, x = BF-ED/AD-BC, y = EC-AF/AD-BC가 됩니다.

그리고 AD-BC가 0일 경우 나눗셈이 안되서 예외처리를 하였는데, 다른 분의 풀이를 보니 두 직선이 평행일때 AD-BC가 0이라고 합니다.
또한 BF-ED와 EC-AF를 AD-BF와의 나머지가 0이 아니라면 정수의 교차점이 아니기 때문에 이 두가지의 경우를 제외하는 좌표를 list에 저장하고 최대x, 최소x, 최대y, 최소y를 갱신해줍니다.

모든 교차점을 찾았다면 각 최대,최소의 좌표로 별을 보여줄 범위를 구하기 위한 높이(maxY-minY+1)와 넓이(maxX-minX+1)를 구해줍니다.

그 후 교차점을 범위의 기준에 맞게 x축은 x-minX로 y축은 maxY-y로 갱신해줍니다.
그리고 StringBuilder를 통해 갱신된 y축의 x의 .을 *로 변경해 주면 됩니다.

그리고 주어지는 좌표가 최대 100000, 최소 -100000이기 때문에 교차점 계산시 int범위를 넘어갈 수 있기 때문에 long으로 선언해주어야하고 별을 표시하는 범위는 1000*1000 이하로 주어진다고 했기 때문에 별을 표시하는 범위를 구할땐 int로 변경해주면 됩니다.

Code

import java.util.List;
import java.util.ArrayList;
class Solution {
    public String[] solution(int[][] line) {
        long minY = Long.MAX_VALUE;
		long maxY = Long.MIN_VALUE;
		long minX = Long.MAX_VALUE;
		long maxX = Long.MIN_VALUE;

		//교차점 저장
		List<int[]> point = new ArrayList<>();
		for(int i=0;i<line.length;i++){
			long A = line[i][0];
			long B = line[i][1];
			long E = line[i][2];
			for(int j=i+1;j<line.length;j++){
				long C = line[j][0];
				long D = line[j][1];
				long F = line[j][2];

				long adbc = A*D-B*C;
				long bfed = B*F-E*D;
				long ecaf = E*C-A*F;

				if(adbc==0) continue; // 비교대상과 평행
				if(bfed%adbc != 0 || ecaf%adbc!=0) continue; //좌표가 정수가 아님

				long x = bfed/adbc;
				long y = ecaf/adbc;

				point.add(new int[]{(int)x, (int)y});

				//별표의 범위를 구하기 위한 각 좌표의 최대,최소값
				minY = Math.min(minY, y);
				maxY = Math.max(maxY, y);
				minX = Math.min(minX, x);
				maxX = Math.max(maxX, x);
			}
		}

		//별 표시 범위의 높이와 넓이
		int high = (int)(maxY-minY+1);
		int weight = (int)(maxX-minX+1);

		//별 표시 범위를 StringBuilder를 통해 .으로 초기화한다.
		StringBuilder[] map = new StringBuilder[high];
		for(int y = 0;y<high;y++){
			StringBuilder sb = new StringBuilder();
			for(int x = 0; x<weight;x++){
				sb.append(".");
			}
			map[y] = sb;
		}

		for(int[] p : point){
			int x = p[0];
			int y = p[1];
	
    		//별 표시 범위를 기준으로 교차점 좌표를 갱신해준다.
			int ny = (int)maxY-y;
			int nx = x-(int)minX;

			//갱신한 교차점 좌표의 .을 *로 변경
			map[ny].setCharAt(nx,'*');
		}

		String[] answer = new String[map.length];
		for(int i=0;i<map.length;i++){
			answer[i] = map[i].toString();
		}

		return answer;
    }
}