[프로그래머스] 교점에 별 만들기 - JAVA

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

---

 
 
좌표 변환 때문에 은근히 헷갈리는 문제였다. 문제 자체는 단순한데, 수학 좌표를 배열 인덱스로 바꾸는 부분에서 뇌정지가 왔다.
 

문제 요약

• 여러 개의 직선이 주어진다. 각 직선은 Ax + By + C = 0 형태로 [A, B, C]로 표현된다.
• 이 직선들의 교점 중에서 x, y가 둘 다 정수인 점만 찾는다.
• 그 교점들을 격자(2차원 배열)에 *로 찍고, 나머지는 .으로 채운다.
• 완성된 격자를 String[]으로 반환한다.

즉 흐름은 이렇다: 교점 구하기 → 정수 교점만 걸러내기 → 격자 만들기 → 별 찍기 → 문자열로 변환.

 

풀이 순서

 

1. 모든 직선 쌍의 교점 구하기

직선이 여러 개니까, 모든 두 직선 쌍을 뽑아서 교점을 계산한다. (이중 for문, j는 i+1부터 시작해서 같은 쌍 중복 방지)
이때 두 직선의 교점 공식을 활용해야한다. 

x = (b1*c2 - b2*c1) / (a1*b2 - a2*b1)
y = (a2*c1 - a1*c2) / (a1*b2 - a2*b1)

여기서 x % 1 != 0 이거나 y % 1 != 0이면 정수가 아니므로 버린다. 정수인 교점만 리스트에 저장한다.

⚠️ 좌표 값이 커질 수 있어서 long 타입을 써야 오버플로가 안 난다.

 

2. 격자의 크기 정하기 (최소/최대 좌표 찾기)

 
교점들이 흩어져 있으니, 이걸 다 담을 수 있는 사각형 격자가 필요하다. 그러려면 교점들 중 가장 작은 좌표(min) 와 가장 큰 좌표(max) 를 찾아야 한다.

int width  = (int)(maximum.x - minimum.x + 1);  // 가로 칸 수
int height = (int)(maximum.y - minimum.y + 1);  // 세로 칸 수

3. 격자 만들고 .으로 채우기

char[][] arr = new char[height][width];
for (char[] row : arr) Arrays.fill(row, '.');

4. 교점 위치에 * 찍기

int x = (int)(p.x - minimum.x);     // 열
int y = (int)(maximum.y - p.y);     // 행
arr[y][x] = '*';

5. char[][] → String[] 변환 후 반환

String[] result = new String[arr.length];
for (int i = 0; i < result.length; i++) {
    result[i] = new String(arr[i]);
}
return result;

 
 
 

내가 헷갈렸던 포인트

1. width / height에 왜 +1을 하는지

"울타리 기둥(fencepost) 문제" 때문이다.
x좌표가 0부터 5까지 있다고 하면:

0  1  2  3  4  5

두 끝의 거리는 5 - 0 = 5지만, 실제 칸의 개수는 0,1,2,3,4,5 → 6개다. 양 끝을 둘 다 포함해야 하니까 최대 - 최소 + 1을 해줘야 정확한 칸 수가 나온다.

 

2. x, y를 배열 인덱스로 바꾸는 부분 

int x = (int)(p.x - minimum.x);   // 열
int y = (int)(maximum.y - p.y);   // 행

 
 
왜 x는 minimum을 빼고, y는 maximum에서 빼는지가 핵심이다. 이유는 수학 좌표계와 배열의 방향이 다르기 때문이다.
 
 
 

	수학 방향	배열 방향	방향	기준
x (열)	오른쪽 ↑	오른쪽 ↑	같음	p.x - minimum.x
y (행)	위쪽 ↑	아래쪽 ↑ (위가 0)	반대	maximum.y - p.y

x (열) — 방향이 같으니까 minimum을 뺀다

배열 열은 0부터 시작해야 한다. 교점 x가 3, 4, 5라면 제일 작은 값(3)을 0으로 끌어내리면 된다.

3 - 3 = 0
4 - 3 = 1
5 - 3 = 2

→ x = p.x - minimum.x

y (행) — 방향이 반대니까 maximum에서 뺀다

수학에서 y는 위로 갈수록 크지만, 배열 행은 아래로 갈수록 크다(맨 위가 행 0). 방향이 반대다.
교점 y가 5, 6, 7이라면, 수학적으로 7이 제일 위에 있는 점 → 배열에서는 행 0(맨 위)이 되어야 한다.
만약 minimum(5)을 빼면 위아래가 뒤집힌다:

7 - 5 = 2   ← 제일 높은 점이 맨 아래로... ✗
5 - 5 = 0   ← 제일 낮은 점이 맨 위로... ✗

그래서 maximum(7)에서 빼준다:

7 - 7 = 0   ← 제일 높은 점이 맨 위 ✓
7 - 5 = 2   ← 제일 낮은 점이 맨 아래 ✓

→ y = maximum.y - p.y
maximum.y - p.y의 "빼는 순서가 반대인 것"이 바로 위아래를 뒤집어주는 역할을 한다. 이게 이 문제의 제일 큰 고비였다.

 

new String(arr[i])

 
arr은 char[][]라서 arr[i]는 한 줄, 즉 char[]이다. 그런데 반환 타입은 String[]이라 문자열로 합쳐야 한다.new String(char[])는 char 배열을 하나의 문자열로 이어붙이는 생성자다.

char[] chars = {'*', '.', '.', '*'};
String s = new String(chars);   // "*..*"

String.valueOf(arr[i])로 써도 결과는 똑같다.
 
 
 

---

전체 코드

import java.util.*;

class Solution {
    private static class Point {
        public final long x, y;
        private Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    private Point intersection(long a1, long b1, long c1,
                               long a2, long b2, long c2) {
        double x = (double)(b1*c2 - b2*c1) / (a1*b2 - a2*b1);
        double y = (double)(a2*c1 - a1*c2) / (a1*b2 - a2*b1);
        if (x % 1 != 0 || y % 1 != 0) return null;
        return new Point((long)x, (long)y);
    }

    private Point getMinimumPoint(List<Point> points) {
        long x = Long.MAX_VALUE, y = Long.MAX_VALUE;
        for (Point p : points) {
            if (p.x < x) x = p.x;
            if (p.y < y) y = p.y;
        }
        return new Point(x, y);
    }

    private Point getMaximumPoint(List<Point> points) {
        long x = Long.MIN_VALUE, y = Long.MIN_VALUE;
        for (Point p : points) {
            if (p.x > x) x = p.x;
            if (p.y > y) y = p.y;
        }
        return new Point(x, y);
    }

    public String[] solution(int[][] line) {
        List<Point> points = new ArrayList<>();
        for (int i = 0; i < line.length; i++) {
            for (int j = i + 1; j < line.length; j++) {
                Point intersection = intersection(
                    line[i][0], line[i][1], line[i][2],
                    line[j][0], line[j][1], line[j][2]);
                if (intersection != null) points.add(intersection);
            }
        }

        Point minimum = getMinimumPoint(points);
        Point maximum = getMaximumPoint(points);

        int width  = (int)(maximum.x - minimum.x + 1);
        int height = (int)(maximum.y - minimum.y + 1);

        char[][] arr = new char[height][width];
        for (char[] row : arr) Arrays.fill(row, '.');

        for (Point p : points) {
            int x = (int)(p.x - minimum.x);
            int y = (int)(maximum.y - p.y);
            arr[y][x] = '*';
        }

        String[] result = new String[arr.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = new String(arr[i]);
        }
        return result;
    }
}

 
 
 

정리

 

• 이 문제의 핵심은 흩어진 정수 좌표를 0부터 시작하는 배열 인덱스 공간으로 옮기는 것.
• +1은 칸 개수를 정확히 세기 위한 것(fencepost).
• x는 방향이 같아서 minimum을, y는 방향이 반대라 maximum을 기준으로 뺀다.
• 마지막에 char[][]를 String[]으로 변환해서 반환.

y축 뒤집기만 이해하면 나머진 어렵지 않은 문제였다. 근데 이 y축 뒤집기를 스스로 생각해내기가 어려운 것 같다. 책 설명 없었으면 1시간 넘게 걸렸을 듯...