[프로그래머스]level 2: 교점에 별 만들기_Java(위클리 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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

---

입출력 예

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]]	["*"]

---

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

직선 y = 1, x = 1, x = -1는 다음과 같습니다.

(-1, 1), (1, 1) 에서 교점이 발생합니다.

따라서 정답은

"*.*"

입니다.

 

입출력 예 #3

직선 y = x, y = 2x는 다음과 같습니다.

(0, 0) 에서 교점이 발생합니다.

따라서 정답은

"*"

입니다.

 

입출력 예 #4

직선 y = x, y = 2x, y = 4x는 다음과 같습니다.

(0, 0) 에서 교점이 발생합니다.

따라서 정답은

"*"

입니다.

---

참고 사항

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

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

 

---

>문제 풀이

* 프로그래머스 위클리 챌린지 10주차 문제입니다.

 

문제에서 두 직선의 교점을 구하는 식을 줬습니다.

x= (BF-ED)/(AD-BC)

y= (EC-AF)/(AD-BC)

​

쉬운 증명이지만, 문제 풀이 전에 간단히 설명하고 넘어가겠습니다.

① Ax+By+E=0

② Cx+Dy+F=0

-----------------------

① x= -(By+E)/A

② x= -(Dy+F)/C

1, 2번 식을 통해서 (By+E)*C=(Dy+F)*A

(BC-AD)*y = (AF-CE)

y=(AF-CE)/(BC-AD)

같은 방법으로 x를 구할 수 있습니다.

​

---

 

자 이제 풀이에 관해,

​

1) for 문을 돌면서 두 직선들의 교점을 구하고, 구한 교점들을 hashset에 넣어줍니다.

1-1) (AD-BC)==0 이면, 두 직선은 평행하다고 볼 수 있습니다.

(만약, 분자가 0일 경우 두 직선이 겹친다는 소리인데, 문제에서 이런 경우의 입력은 안주어진다고 했으니 신경 안써줘도 됩니다.)

1-2) 두 교점이 정수인지 아닌지 판별하여, 구한 교점 x, y가 모두 정수인 것만 HashSet<Point> 에 넣어줍니다.

1-3) 구한 교점으로 x의 최댓값과, 최솟값, y의 최댓값과 최솟값을 구합니다. (=갱신해나갑니다.)

​

2) 구한 maxx, maxy, minx, miny로 구한 교점들을 넣을 판의 height와 width를 구합니다.

3) answer= new String[height] 로 판을 만들어주고, 일단 점으로 채워줍니다. ex) "........~........"

4) set에 넣어뒀던 교점들을 순회하며 answer판에 "*" 별을 넣어줍니다.

 

 

 

>전체 코드

 

import java.util.HashSet;
import java.util.Arrays;
class Solution {
    static long minx= Long.MAX_VALUE, miny= Long.MAX_VALUE;
    static long maxx= Long.MIN_VALUE, maxy= Long.MIN_VALUE;
    
    public String[] solution(int[][] line) {
        String[] answer = {};
        HashSet<Point> pSet= new HashSet<>();
        
        //x= (bf-ed)/(ad-bc)
        //y= (ec-af)/(ad-bc)
        long x, y;
        for(int i=0; i<line.length-1; 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;
                if(adbc==0) continue; //비교대상 직선과 평행함
                
                long bfed= b*f-e*d;
                if(bfed%adbc!=0) continue; //x가 정수가 아님
                
                long ecaf= e*c-a*f;
                if(ecaf%adbc!=0) continue; //y가 정수가 아님
                
                x= bfed/adbc;
                y= ecaf/adbc;
                pSet.add(new Point(x, y));
                
                minx= Math.min(minx, x);
                miny= Math.min(miny, y);
                maxx= Math.max(maxx, x);
                maxy= Math.max(maxy, y);
            }
        }
        
        long height= maxy-miny+1;
        long width= maxx-minx+1;
        answer= new String[(int)height];
        StringBuilder sb= new StringBuilder();
        for(int i=0; i<width; i++){
            sb.append(".");
        }
        
        Arrays.fill(answer, sb.toString());
        
        long nx, ny;
        for(Point p: pSet){
            ny= maxy-p.y;
            nx= p.x-minx;
            answer[(int)ny]= answer[(int)ny].substring(0, (int)nx)+"*"
                        +answer[(int)ny].substring((int)nx+1);
        }
        
        return answer;
    }
    
    public class Point{
        long x;
        long y;
        public Point(long x, long y){
            this.x= x;
            this.y= y;
        }
    }
}

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

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