[프로그래머스,Java] Level2: 교점에 별 만들기 [위클리 챌린지 10주차]

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

코딩테스트 연습 - 10주차

 

문제분석

 

문제에서 여러개의 직선을 입력으로 주어집니다.

 

여러개의 직선이 만나는 점을 교점이라고 한다면, 그 정수로된 교점을 찍은 문자열을 출력해주세요.

최소한의 크기로 줄여야합니다.

 

 

이 공식 없었으면 Level3

 

1.모든 직선이 만나는 교점을 구할려면,  직선 2개를 집어서 만나는점을 출력하면된다.

 

즉, NC2  N개의 직선에서 2개를뽑는 조합을 구하면된다.

 

근데 2개만 뽑는 조합은 이중 for문으로 구현이가능하다.for( int i=0 ~)   for(int j=i+1 ~) 식으로 말이다.

 

 

2.직선 2개를 뽑았다면, 교점을 구해야합니다! 

 

참고사항에서 주어진 교점공식을 활용합시다 

 

//여기서 잠깐

첫 입력으로 A B C D E F 숫자들은 다 int형으로 들어옵니다.

각 숫자마다 long형으로 형변환을 꼭해주셔야합니다.

만약, long형으로 변형 안하시면,

EX) A,B,C,D = 100000
분모(denominator)= int(A)Xint(D)<--(여기서 IntOverflow) - int(B)Xint(C)<--(여기서 IntOverflow);

그니깐, 난 10만*10만 =100억을 뽑고싶은데
intOverflow가 떠서 100억이 2147483647(int형 Max값)으로 치환됩니다.

 

->안해주시면 29번 오류뜹니다..네.. (Java라 당했다..)

->파이썬은 이런거 걱정안해도 된다.. 

3.교점 X, Y 좌표가 구하기전에,  정수인지 실수인지를 확인해야하죠

 BF-ED % AD-BC   EC-AF%AD-BC 가 0이 아니면 실수이므로, 이런경우는 뺍시다

 

 정수인 교점들만 모아서, 리스트에 저장해둡시다.

 

4.정수인 교점만 모두 구하셧다면, 점을찍을 판의 크기를 정해야합니다.

 

문제에서 최소한의 크기의 판(별이 무조건 벽에붙는 판)을 만들고싶어합니다.

 

그렇다면, 교점X들의 최소,최대 와 교점 Y들의 최소 최대를 모두 구합니다

 

그림그릴 판의 X값 = 교점X좌표들의 최소 ~ 교점X들의 최대

그림그릴 판의 Y값 = 교점Y좌표들의 최소 ~ 교점Y들의 최대

요렇게 말이죠!

 

5.점을찍을 판을 세팅하셧다면, 점을찍을 차례입니다.

 

첫번째 방법은, 교점X좌표들의 최소 ~ 교점X들의 최대 와 교점Y좌표들의 최소 ~ 교점Y들의 최대 를 돌면서 (2차반복),

 

정수인 교점이 해당하면 스타를 찍고, 아니면 마침표를 찍으면 됩니다.

->근데 3차반복.. (대신 코딩난이도는 쉽다)

 

두번째 방법은, 교점X좌표들의 최소 ~ 교점X들의 최대 와 교점Y좌표들의 최소 ~ 교점Y들의 최대 를 돌면서 (2차반복)

일단 마침표를 찍고

 

반복을 끝낸뒤에, 정수인 교점들을 덫씌우는식 (1차반복)

-> 2차+1차 (대신 코딩난이도는 조금 올라간다.. idx의 위치가 바뀌면서 재설정해줘야함..) 

 

무슨방법을써도 통과는하지만,  효율성은 2번째방법이 낫다.

 

6.점을 모두 찍었다면 완성!

문제풀이

import java.util.*;
 
public class Solution {
 
    public static int startX = Integer.MAX_VALUE;
    public static int endX = Integer.MIN_VALUE;
    public static int startY = Integer.MAX_VALUE;
    public static int endY = Integer.MIN_VALUE;
 
    public String[] solution(int[][] line) {
        List<List<Integer>> list = 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];
                long b = line[i][1];
                long e = line[i][2];
 
                long c = line[j][0];
                long d = line[j][1];
                long f = line[j][2];
                long denominator = (a * d) - (b * c);
                if(denominator == 0) continue;
                
                
                long numerator1 = (b * f) - (e * d);
                long numerator2 = (e * c) - (a * f);
                if(numerator1 % denominator != 0 || numerator2 % denominator != 0) continue;
                
                int x  = (int) (numerator1 / denominator);
                int y = (int) (numerator2 / denominator);
                
                List<Integer> temp = Arrays.asList((int) x, (int) y);
                if(!list.contains(temp)) list.add(temp);
 
                startX = Math.min(startX, (int) x);
                endX = Math.max(endX, (int) x);
                startY = Math.min(startY, (int) y);
                endY = Math.max(endY, (int) y);
            }
        }
 
        List<String> board = new ArrayList<>();
        for(int i=startY; i<=endY; i++) {
            StringBuilder sb = new StringBuilder();
            for(int j=startX; j<=endX; j++) {
                sb.append(".");
            }
            board.add(sb.toString());
        }
 
        for(List<Integer> intersection : list) {
            StringBuilder sb = new StringBuilder(board.get(Math.abs(intersection.get(1) - endY)));
            sb.setCharAt(Math.abs(intersection.get(0) - startX), '*');
            board.set(Math.abs(intersection.get(1) - endY), sb.toString());
        }
 
        String[] answer = new String[board.size()];
        for(int i=0; i<answer.length; i++) {
            answer[i] = board.get(i);
        }
 
        return answer;
    }
}