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

 📌 문제 소개

 

Level 2

 

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

프로그래머스

 

 

 🔍 문제 설명

 

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

 

 📝 풀이 과정

 

이 문제의 요지는 주어진 직선들의 교점을 찾아, 최소 크기의 별이 찍힌 사각형을 구하는 것이다. 중요한 포인트는, 이 최소 크기 사각형 내에서 별을 상대 좌표로 표현하는 것이다. 풀이 과정은 다음과 같이 단계별로 요약할 수 있다. (핵심적인 내용만을 세밀하게 다루었다.)

 

1. 교점 좌표 클래스 선언하기

좌표 클래스를 선언하지 않고도 문제를 해결할 수 있지만 가독성을 높이기 위하여 따로 선언하였다. Set 자료구조에 직접 만든 클래스 타입(Point)의 값을 저장하므로, 좌표가 같을 경우 중복 저장을 피하도록 하려면 Point 클래스 내에서 equals(), hashCode() 메소드를 오버라이딩 해야 한다. 오버라이딩을 하지 않을 경우 Set 내에서 객체의 번지만 비교해서 저장하므로, 교점 좌표가 동일하더라도 중복으로 저장된다. 하지만, 이 문제에서는 중복되는 교점의 좌표 수 가 적은지, 오버라이딩 하지 않아도 시간 초과나 메모리 초과가 일어나지 않는다.

 

2. 교점 좌표 구하기

교점 좌표 구하는 방법은 문제의 참고 사항에 나와있는 내용을 그대로 적용시키면 된다. Ax + By + E = 0, Cx + Dy + F = 0 일 때 교점을 구하는 공식은 아래와 같다.

 

 

여기서 주의사항이 있다. 주어진 A, B, C, D, E, F의 값의 크기가 최대 100,000이므로 각각 곱하는 과정에서 int 범위를 초과하므로 오버플로우가 발생하게 된다. 따라서 (double)(b1*c2-b2*c1)/(a1*b2-a2*b1)과 같이 적으면 오버플로우가 발생하므로 반드시 ((double)b1*c2-b2*c1)/((double)a1*b2-a2*b1) 이렇게 적어야 한다. 그리고, 한 배열을 이중으로 반복시켜야 되는 경우, 두 번째 반복문에서 시작 인덱스를 i+1로 두면 중복을 피할 수 있다.

 

3. 최소 사각형의 가로 세로 길이 구하기

가로길이는 (최대 x좌표 - 최소 x좌표 +1)로 구하면 되고, 세로 길이는 (최대 y좌표 - 최소 y좌표 +1)로 구하면 된다. 참고로 여기서 1을 더하는 이유는 배열 범위를 구할 때 최소 좌표와 최대 좌표를 모두 포함하기 때문이다. 예를 들어 최소 x좌표가 2이고, 최대 x좌표가 4라고 할 때 4-2 = 2이지만 배열에서는 2, 3, 4를 포함하므로 1을 더해야 한다.

 

4. 교점을 만든 사각형에 비례해서 상대좌표로 변환하고 별 찍기

어떻게 보면 이 문제의 핵심이라고 할 수 있다. 일반적으로 이중배열은 위에서 시작해서 아래로 형성되는 것으로 묘사한다. 따라서 상대좌표에서 왼쪽 위를 (0,0)이라고 두면 x 좌표는 (현재 x 좌표 - 최소 x좌표)이고, y 좌표는 (최대 y 좌표 - 현재 y 좌표)이다. y 좌표 구하는 방식이 일반적인 경우와 비교했을 때 역순인 이유는 아까 말했다시피 왼쪽 위가 시작 좌표이기 때문이다. 참고로 Set에서 값은 향상된 for문으로 가져오면 된다.

 

5. 이중 char 배열을 단일 String 배열로 변환해서 반환하기

String의 생성자에 char 배열을 넣으면 String으로 변환된다.

 

 

 

 🛎️ 정답 코드

 

import java.util.*;

class Solution {
    
    public String[] solution(int[][] line) {
        Set<Point> intPoint = new HashSet<>();
        
        long highX=Long.MIN_VALUE, lowX=Long.MAX_VALUE, highY=Long.MIN_VALUE, lowY=Long.MAX_VALUE; // 미리 정반대의 극값으로 설정

        for (int i=0; i<line.length; i++) {
            for (int k=i+1; k<line.length; k++) {
                Point temp = interSectPoint(line[i][0], line[i][1], line[i][2], line[k][0], line[k][1], line[k][2]);

                if (temp != null) {
                    intPoint.add(temp);
                    
                    // 상하좌우 최대,최소값 구하기
                    highX = Math.max(highX, temp.x);
                    lowX = Math.min(lowX, temp.x);
                    highY = Math.max(highY, temp.y);
                    lowY = Math.min(lowY, temp.y);
                }
            }
        }

        int row = (int)(highX - lowX + 1);
        int column = (int)(highY - lowY + 1);

        // 사각형 생성
        char[][] square = new char[column][row];
        for (char[] temp : square) {
            Arrays.fill(temp, '.');
        }

        // 사각형에 별 찍기
        for (Point p : intPoint) {
            int x = (int)(p.x - lowX);
            int y = (int)(highY - p.y);

            square[y][x] = '*';
        }

        // 이중 char 배열을 단일 String 배열로 옮기기
        String[] answer = new String[square.length];
        for (int i=0; i<square.length; i++) {
            answer[i] = new String(square[i]);
        }

        return answer;
    }

    private static class Point {
        public long x,y;

        Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
        
        // Set 내에서 Point 타입 값의 중복을 없애기 위해 equals, hashCode 메소드 오버라이드
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o==null || getClass()!=o.getClass()) return false;
            Point p = (Point) o;
            return Objects.equals(x, p.x) && Objects.equals(y, p.y);
        }
        
        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    // 교점 구하기
    private static Point interSectPoint(int a1, int b1, int c1, int a2, int b2, int c2) {

        double x = ((double)b1*c2-b2*c1)/((double)a1*b2-a2*b1); // 분모 분자 각각을 double로 변환해줘야함 (곱하는 과정에서 int 범위를 초과)
        double y = ((double)a2*c1-a1*c2)/((double)a1*b2-a2*b1); 

        if (x%1!=0 || y%1!=0 || (double)(a1*b2-a2*b1)==0) {return null;}

        return new Point((long) x, (long) y);
    }
}