프로그래머스 LV2. 교점에 별 만들기 (자바)

🍀 문제

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

입출력 예 설명

입출력 예 #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주차_교점에 별 만들기 | 프로그래머스 (programmers.co.kr)

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

 

😊 나의 코드

import java.util.*;
class Solution {
    public String[] solution(int[][] line) {
        HashSet<String> set = new HashSet();
        long maxX  = Long.MIN_VALUE;
        long maxY = Long.MIN_VALUE;
        long minX = Long.MAX_VALUE;
        long minY = Long.MAX_VALUE;

        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];
                if(a*d-b*c != 0) {
                    long x = (b*f-e*d)/(a*d-b*c);
                    long y = (e*c-a*f)/(a*d-b*c);
                    if((b*f-e*d)%(a*d-b*c)==0 && (e*c-a*f)%(a*d-b*c)==0) {
                        maxX = Math.max(maxX, x);
                        maxY = Math.max(maxY, y);
                        minX = Math.min(minX, x);
                        minY = Math.min(minY, y);
                        set.add(x+","+y);
                    }
                }
            }
        }

        String[] answer = new String[ (int) (maxY-minY+1)];
        int index = 0;
        for(long i=maxY; i >= minY; i--) {
            String s = "";
            for(long j=minX; j <= maxX; j++) {
                if(set.contains(j+","+i)) {
                    s += "*";
                }else {
                    s+=".";
                }

            }
            answer[index] = s;
            index++;
        }

        return answer;
    }
}

1. 교점은 두 직선이 만났을때 생기므로 직선 2개씩 교점이 있는지 확인한다.

 

2. 교점의 수식은 참고사항에 나와있는 대로 

이므로 이 계산을 해서 정수인 교점만 "x,y" 형태의 문자열로 HashSet에 저장했다.

(HashSet은 중복이 안되므로 HashSet을 선택)

 

3. 최소한의 크기로 별을 표기해야 하기에

교점의 최대 최소 x좌표 y좌표를 각각 구해서 (maxX, maxY, minX, minY)

그만큼 for문으로 돌면서 교점이면 별(*) 표시를 아니면 점(.) 표시를 해서 answer답변에 저장하고 리턴했다.

 

 

 

뭔가 이차함수 개념이 나오면서 어려워보였는데,

교점을 구하는 수식이 나와있어 수식계산을 하면서 풀면 생각보다 교점을 구하는 것은 어렵지 않았다.

다만 int 데이터형을 사용하니 마지막 테스트에서 오류가 생겼다.

데이터셋을 넘는 숫자가 들어가서 생기는 오류로

long형으로 바꿔서 제출하니 통과가 되었다.

 

최대값이나 최소값의 초기값을 어떻게 설정할까 고민했는데,

Long.MIN_VALUE나 Long.MAX_VALUE을 사용하여 초기화해주었다.