[ 프로그래머스 / 위클리 챌린지 ] 교점에 별 만들기 - solved java

https://programmers.co.kr/learn/courses/30/lessons/87377?language=java 

코딩테스트 연습 - 교점에 별 만들기

 

• 교점에 별 만들기

문제 설명

Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.

예를 들어, 다음과 같은 직선 5개를

• 2x - y + 4 = 0
• -2x - y + 4 = 0
• -y + 1 = 0
• 5x - 8y - 12 = 0
• 5x + 8y + 12 = 0

좌표 평면 위에 그리면 아래 그림과 같습니다.

이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)입니다.

만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.

위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다.

"..........." ".....*....." "..........." "..........." ".*.......*." "..........." "..........." "..........." "..........." ".*.......*." "..........."

이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.

따라서 정답은

"....*...." "........." "........." "*.......*" "........." "........." "........." "........." "*.......*"

입니다.

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• line의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다.
  • line의 가로(열) 길이는 3입니다.
  • line의 각 원소는 [A, B, C] 형태입니다.
  • A, B, C는 -100,000 이상 100,000 이하인 정수입니다.
  • 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
  • A = 0이면서 B = 0인 경우는 주어지지 않습니다.
• 정답은 1,000 * 1,000 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

---

입출력 예

lineresult

[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]	["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]
[[0, 1, -1], [1, 0, -1], [1, 0, 1]]	["*.*"]
[[1, -1, 0], [2, -1, 0]]	["*"]
[[1, -1, 0], [2, -1, 0], [4, -1, 0]]	["*"]

 

---

참고 사항

Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.

 

import java.util.*;
class Solution {
    public String[] solution(int[][] line) {
        String[] answer = {};
        ArrayList<int[]> al = new ArrayList<int[]>();// 교점 담을 배열 
        int L = line.length;
        int minx = Integer.MAX_VALUE,miny = Integer.MAX_VALUE;
        int maxx = Integer.MIN_VALUE,maxy = Integer.MIN_VALUE;
        for(int i = 0; i< L ;i++){// 조합 만들기
            for(int j = i+1; j<L ; j++){// 두개의 교점
                long a = line[i][0],b=line[i][1],e = line[i][2];
                long c = line[j][0],d=line[j][1],f = line[j][2];
                long adbc = (1L*a*d) - (1L*b*c);
                if(adbc==0) continue;
                long bfed = (1L*b*f)-(1L*e*d);
                long ecaf = (1L*e*c)-(1L*a*f);
                if(bfed%adbc!=0 || ecaf%adbc!=0) continue;
                int x = (int)(bfed / adbc);
                int y = (int)(ecaf / adbc);
                al.add(new int[]{x,y});
                minx = x<minx?x:minx;
                maxx = x>maxx?x:maxx;
                miny = y<miny?y:miny;
                maxy = y>maxy?y:maxy;
            }// 교점 다 찾기 
        }
        int R = maxx-minx+1;
        int C = maxy-miny+1;
        char[][]ans = new char[C][R];
        for(int i = 0; i< C; i++){
            for(int j=0; j<R; j++){
                ans[i][j] = '.';
            }
        }
        for(int[] a : al){
            System.out.print(a[0]+","+a[1]+" :: ");
            int r = a[0]-minx;
            int c = maxy-a[1];
            System.out.println(c+", "+r);
            ans[c][r] = '*';
        }
        answer = new String[C];
        for(int i = 0; i< C; i++){
            String str = "";
            for(int j = 0; j< R; j++){
                str+=ans[i][j];
            }
            answer[i]= str;
        }
        return answer;
    }
}

 

문제 풀이 

먼저 우선 값들을 담을 ArrayList를 선언해 준다. al은 내가 자주 쓰는 ArrayList의 약자이담.

그리고 이후 고정 값으로 이용할 값들을 선언해준다. 
min, max값들은 이후 네모 칸을 딱 맞게 만드는데 이용한다. 

그리고 가장 중요한 두 선의 교점을 찾기 위해서 반복문을 돌려준다. 

그리고 테스트 케이스 27,28을 풀기 위해서는 이 부분이 중요한데, ... 사실 여기는 int여도 상관은 없다..

예시로 준 이 식에 맞춰 풀면 편해보여서 abcd알파벳을 모두 선언해 준다. 

그리고 이제 반드시 Long으로 선언해 줘야 하는 부분이 

여기가 된다. 이 a*d를 했을 곱하는 값들이 int보다 커 질 수 있기 때문에 1L으로 반드시 변환해서 계산을 해줘야 한다.
저렇게 앞에 1L까지 붙여줘야 제대로 계산이 된다..

이 값이 0이면 교점이 없으니 걍 continue한다. 

그리고 정수로만 떨어져야 한다고 했으니, 이 값들도 모두 계산 했다가 나누어 떨어지지 않으면 continue하도록 한다. 
이걸 멀 쪼끔 잘못 짰을때 테케를 앞에 1,2 부터 틀리기 시작했는데, 뭐 이렇게 하면 되더라.. long과 int와 double과 막 어쩌고 저쩌고 해서 그랬던거 같다..

그리고 이후 x값과 y값을 구해서 al에 넣어준다 Set으로 넣으면 중복값이 없어서 더 빠르게 돌았겠지만 꺼내올떄 반복문 돌기 편하려고 array로 그냥 했다. 시간초과만 안뜨면 되었지

그리고 String배열로 출력해야 하니까 열심히 최소값이랑 최대값을 찾았다. 

이렇게 열심히 찾은 min과 max의 값이 가로 길이 R과 세로 길이 C가 된다. 이거는 좀 헷갈리게 코딩했네, 대문자 X랑 Y로 둘껄.. 

그리고 기존의 값들에 우선 전부 '.'를 넣어준다. 

그리고는 아까 al에 넣어둔 교점들을 열심히 돌면서 , a[0]-min 하면 앞에서 얼마나 떨어진지 나오니, 그 값이 r좌표가 되고, maxy-a[1]하면 c좌표가 되니까 이 값들을 '*'로 바꿔준다. 

그리고 이제 바꿔진 값들을 출력형식에 맞게 열심히 변환해주면,

answer가 나오게된다.