[ 프로그래머스 / Programmers Weekly Challenge ] 10주차_교점에 별 만들기 ( 자바 / JAVA )

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

코딩테스트 연습 - 10주차_교점에 별 만들기

 

문제

---

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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

참고사항

---

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

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

풀이

---

1️⃣ 위 의 식을 이용해서 정수인 교점을 구해준다.

 ⁂ AD-BC != 0 인 교점 만 ‼️

2️⃣ 교점의 좌표들 중 최대값과 최솟갑을 구해준다.

3️⃣ 높이와 너비에 맞게 '.' 를 찍는다.

4️⃣ 각 좌표에 맞게 별을 찍는다.

 

끄틍~🙋‍♀️

 

코드

---

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

public class Main_P_10주차_교점에별만들기 {

    static class coordinate{
        int x;
        int y;

        coordinate(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    static int startX = Integer.MAX_VALUE;
    static int startY = Integer.MAX_VALUE;
    static int endX = Integer.MIN_VALUE;
    static int endY = Integer.MIN_VALUE;

    public static String[] solution(int[][] line) {
        String[] answer = {};

        List<coordinate> cList = new ArrayList<>();
        
        for(int i = 0 ; i < line.length ; 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 integerVerification1 = (b*f) - (e*d);
                long integerVerification2 = (e*c) - (a*f);
                if(integerVerification1 % denominator != 0 || integerVerification2 % denominator != 0)  continue;

                coordinate coord = new coordinate((int)(((b*f) - (e*d))/denominator), (int)(((e*c) - (a*f))/denominator));
                if(!cList.contains(coord))
                    cList.add(coord);

                startX = Math.min(startX, coord.x);
                startY = Math.min(startY, coord.y);
                endX = Math.max(endX, coord.x);
                endY = Math.max(endY, coord.y);
            }
        }

        // System.out.println(startX + " " + startY + " " + endX + " " + endY);

        ArrayList<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());
        }

        int yLen = board.size() / 2;
        int xLen = board.get(0).length() / 2;
        for(coordinate c : cList){
            int x = Math.abs(c.x - startX);
            int y = Math.abs(c.y - startY);

            // System.out.println(x + " " + y);

            StringBuilder sb = new StringBuilder(board.get(y));
            board.remove(y);
            sb.setCharAt(x, '*');

            board.add(y, sb.toString());

        }
       
        answer = new String[board.size()];
        for(int i = 0 ; i < board.size() ; i++){
            answer[i] = board.get(board.size()-i-1);
        }
            

        return answer;
    }

    public static void main(String[] args) {
        // int[][] line = {{2, -1, 4}, {-2, -1, 4}, {0,-1,1}, {5,-8,-12},{5,8,12}};
        int[][] line = {{0,1,-1}, {1,0,-1}, {1,0,1}};
        String[] answer = solution(line);
        
        for(String a : answer)
            System.out.println(a);
    }
}