프로그래머스 | Level 2 | 교점에 별 만들기

Programmers | Level 2 | 교점에 별 만들기

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Brute Force

󰧭 Description

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 함수를 완성해주세요.

참고 사항

• Ax + By + E = 0
• Cx + Dy + F = 0

위 두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

• x = (BF - ED) ÷ (AD - BC)
• y = (EC - AF) ÷ (AD - BC)

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

 Constraints

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

󰦕 Examples

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

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        // 직선 쌍의 조합 생성
        List<int[]> combs = new ArrayList<>();
        int left = 0;
        int right = line.length - 1;
        while (left < right) {
            for (int i = right; i > left; i--) {
                int[] comb = new int[]{left, i};
                combs.add(comb);
            }
            left++;
        }
        
        // 교점 저장할 맵과 좌표 범위 초기화
        Map<String, long[]> stars = new HashMap<>();
        long[] range = new long[]{Long.MAX_VALUE, Long.MIN_VALUE, Long.MAX_VALUE, Long.MIN_VALUE};
        combs.forEach(comb -> findStar(line[comb[0]], line[comb[1]], stars, range));
        
        // 최소 사각형 크기로 결과 배열 생성
        int totalRows = (int) (range[3] - range[2] + 1);
        int currRow = totalRows - 1;
        String[] canvas = new String[totalRows];
        for (long i = range[2]; i <= range[3]; i++) {
            StringBuilder sb = new StringBuilder();
            for (long j = range[0]; j <= range[1]; j++) {
                if (stars.containsKey(generateKey(j, i))) sb.append("*");
                else sb.append(".");
            }
            canvas[currRow] = sb.toString();
            currRow--;
        }
        
        return canvas;
    }
    
    // 교점 계산
    private void findStar(int[] line1, int[] line2, Map<String, long[]> stars, long[] range) {
        long a = line1[0];
        long b = line1[1];
        long e = line1[2];
        long c = line2[0];
        long d = line2[1];
        long f = line2[2];
        
        // 두 직선이 평행한지 확인
        if (isParallel(a, b, c, d)) return;
        
        // 교점 좌표 계산
        Double x = (b * f - e * d) * 1.0 / (a * d - b * c);
        Double y = (e * c - a * f) * 1.0 / (a * d - b * c);
        
        // 정수 좌표 여부 확인
        if (!isDivisible(x) || !isDivisible(y)) return;
        
        long[] star = new long[]{x.longValue(), y.longValue()};
        stars.put(generateKey(star[0], star[1]), star);
        
        // 좌표 범위 갱신
        range[0] = Math.min(range[0], star[0]);
        range[1] = Math.max(range[1], star[0]);
        range[2] = Math.min(range[2], star[1]);
        range[3] = Math.max(range[3], star[1]);
    }
    
    // 두 직선의 평행 여부 확인
    private boolean isParallel(long a, long b, long c, long d) {
        long ad = Math.multiplyExact(a, d);
        long bc = Math.multiplyExact(b, c);
        return ad - bc == 0;
    }
    // 정수 좌표 여부 확인
    private boolean isDivisible(Double number) {
        return Math.floor(number) == number;
    }
        
    // 좌표 키 생성
    private String generateKey(long x, long y) {
        return x + "," + y;
    }
}

 Approaches

이 문제는 직선의 교점을 구하여 정수 좌표인 지점에 별을 그리는 문제입니다. 각 직선 쌍의 교점을 찾아 정수 좌표로 변환하고, 최소 크기의 사각형 내에서 별을 그릴 수 있도록 좌표를 갱신합니다.

1. 문제 분석

이 문제는 여러 직선이 주어졌을 때, 두 직선의 교점을 찾아 정수 좌표에만 별을 표시하는 것입니다. 각 직선은 Ax + By + C = 0의 형태로 주어지며, 이를 기반으로 각 직선 쌍의 교점을 계산해야 합니다. 중요한 점은, 유효한 교점은 정수 좌표여야 하며, 평행한 직선 쌍은 교점이 없다는 점입니다. 문제를 풀기 위해 다음과 같은 수학적 원리와 검토 과정이 필요합니다.

문제 하단의 참고 사항에 명시된 크래머 공식을 활용하여, 두 직선이 A1x + B1y + C1 = 0과 A2x + B2y + C2 = 0의 형태로 주어졌을 때, 두 직선의 교점 (x, y) 좌표는 다음과 같이 계산됩니다:

• 분모: A1 * B2 - A2 * B1
• x좌표: (B1 * C2 - B2 * C1) / (A1 * B2 - A2 * B1)
• y좌표: (C1 * A2 - C2 * A1) / (A1 * B2 - A2 * B1)

이때 분모가 0이면 두 직선은 평행하므로 교점이 존재하지 않습니다. 따라서, 두 직선이 평행한지 여부를 우선 확인하여, 평행하지 않은 직선들에 대해서만 교점을 계산하게 됩니다.

교점이 유효하려면 x, y 좌표가 정수 좌표여야 합니다. 위의 계산으로 얻은 x와 y가 정수로 나누어 떨어지는지 확인하여, 정수 좌표가 아닌 교점은 제외합니다. 이 과정에서 소수점이 발생할 수 있는데, 소수점 확인을 통해 나머지 없이 정확히 나누어지는지 검사해야 합니다.

• 숫자 범위: 문제에서 각 직선의 계수는 -100,000에서 100,000까지의 정수로 주어집니다. 따라서 계산 과정에서 발생하는 값이 매우 커질 수 있으므로 오버플로우를 피하기 위해 Long 타입을 사용하여 계산해야 합니다.
• 최소 크기의 격자 찾기: 교점이 모두 구해지면, 모든 별을 포함하는 최소한의 격자 범위를 설정하여, 이를 기준으로 격자를 그립니다. 격자의 최소 크기를 설정하는 과정은 교점들의 최솟값 및 최댓값을 확인하여 범위를 정합니다.
• 효율성 고려: 직선의 개수가 많을 경우, 모든 직선 쌍을 계산하면 최대 약 500,000개의 조합이 발생할 수 있습니다. 따라서 각 단계에서 불필요한 연산을 줄이는 최적화가 중요합니다.

2. 접근 방식

문제를 효율적으로 해결하기 위해 다음 단계를 따릅니다:

1. 직선 쌍의 조합 생성: 주어진 모든 직선의 쌍을 생성하여 각 쌍에서 교점을 찾습니다.
2. 교점 계산 및 정수 여부 확인: 각 직선 쌍의 교점을 구해 정수 좌표인지 확인합니다.
3. 교점 좌표 저장 및 범위 갱신: 유효한 교점 좌표를 맵에 저장하고, 좌표의 범위를 갱신하여 최종 격자 크기를 결정합니다.
4. 격자 생성 및 반환: 구한 교점 범위에 따라 격자를 생성하고, 각 교점에 별을 표시하여 결과를 반환합니다.

3. 두 직선 조합 생성

이 문제에서는 모든 직선 쌍을 조합하여 가능한 교점을 계산합니다. 직선들의 교점은 한 쌍의 직선에서만 발생하므로, 각 직선의 조합을 생성하는 단계가 필요합니다. 이를 위해 첫 번째 직선부터 마지막 직선까지의 쌍을 반복적으로 선택하여 조합을 형성합니다. 이러한 방식으로 모든 가능한 직선 쌍이 탐색되며, 중복을 방지하기 위해 각 쌍은 특정한 규칙에 따라 순차적으로 생성됩니다. 이를 통해 불필요한 반복을 줄이고 효율적으로 조합을 생성할 수 있습니다.

List<int[]> combs = new ArrayList<>();  // 모든 직선 쌍의 인덱스 조합을 저장할 리스트
int left = 0;  // 조합의 시작 인덱스
int right = line.length - 1;  // 조합의 끝 인덱스

// 모든 가능한 직선 쌍의 인덱스 조합 생성
while (left < right) {
    for (int i = right; i > left; i--) {
        int[] comb = new int[]{left, i};  // 현재 조합을 배열로 생성
        combs.add(comb);  // 조합을 리스트에 추가
    }
    left++;  // 다음 시작 인덱스로 이동
}

4. 두 직선의 교점 좌표 저장 및 좌표 범위 갱신

각 직선 쌍에 대해 교점을 계산한 후, 해당 교점이 정수 좌표일 경우에만 저장합니다. 교점은 크래머 공식으로 계산되며, 계산된 x, y 좌표가 정수로 나누어 떨어질 때만 유효한 교점으로 간주합니다. 교점이 유효한 경우 이를 맵에 저장하고, 별이 그려질 격자판의 최소 범위를 계산합니다. 이를 통해 교점 좌표들의 최소 및 최대 범위를 추적하여 최종적으로 별이 포함되는 최소 크기의 격자판을 생성할 수 있습니다.

Map<String, long[]> stars = new HashMap<>();  // 두 직선의 교점 위치 저장
long[] range = new long[]{Long.MAX_VALUE, Long.MIN_VALUE, Long.MAX_VALUE, Long.MIN_VALUE};  // 사각형의 최소 범위 저장
combs.forEach(comb -> findStar(line[comb[0]], line[comb[1]], stars, range));

유효한 교점이 발견되면 중복 제거와 빠른 탐색을 위해 해당 좌표를 문자열 형식의 키로 변환하여 해시맵에 저장합니다. 그리고 격자 크기를 위한 좌표 범위도 함께 갱신합니다. 해시맵과 범위 갱신을 통해 모든 교점을 저장하는 동시에, 별이 그려질 최소 격자의 크기도 추적할 수 있습니다.

private void findStar(int[] line1, int[] line2, Map<String, long[]> stars, long[] range) {
    long a = line1[0];
    long b = line1[1];
    long e = line1[2];
    long c = line2[0];
    long d = line2[1];
    long f = line2[2];
    
    if (isParallel(a, b, c, d)) return;  // 평행한 경우 교점 없음

    // 교점 x, y 계산
    Double x = (b * f - e * d) * 1.0 / (a * d - b * c);
    Double y = (e * c - a * f) * 1.0 / (a * d - b * c);
    
    if (!isDivisible(x) || !isDivisible(y)) return;  // 정수 좌표가 아닐 경우 제외
    
    long[] star = new long[]{x.longValue(), y.longValue()};
    stars.put(generateKey(star[0], star[1]), star);  // 교점 저장
    
    // 좌표 범위 갱신
    range[0] = Math.min(range[0], star[0]);
    range[1] = Math.max(range[1], star[0]);
    range[2] = Math.min(range[2], star[1]);
    range[3] = Math.max(range[3], star[1]);
}

private boolean isParallel(long a, long b, long c, long d) {
    long ad = Math.multiplyExact(a, d);
    long bc = Math.multiplyExact(b, c);
    return ad - bc == 0;
}

private boolean isDivisible(Double number) {
    return Math.floor(number) == number;
}

private String generateKey(long x, long y) {
    return x + "," + y;
}

5. 최소 크기 격자 생성 및 별 그리기

모든 교점의 범위가 계산되면, 최소한의 크기로 격자를 생성합니다. 루프 조건에 따라 별을 그리는 방향을 지정할 수 있는데, 여기서는 하단에서 상단 순으로 별을 배치하며 구성하였습니다. 각 좌표에서 별이 그려질 위치는 교점 맵을 참조하여 결정되며, 교점이 포함된 위치에는 *을, 교점이 없는 위치에는 .을 표시합니다. 최종적으로 완성된 격자는 문자열 배열로 반환됩니다.

int totalRows = (int) (range[3] - range[2] + 1);  // y 좌표 범위에 따른 총 행 수
int currRow = totalRows - 1;  // 격자의 현재 행을 마지막 행부터 시작
String[] canvas = new String[totalRows];  // 결과 격자

for (long i = range[2]; i <= range[3]; i++) {
    StringBuilder sb = new StringBuilder();
    for (long j = range[0]; j <= range[1]; j++) {
        if (stars.containsKey(generateKey(j, i))) sb.append("*");  // 별을 그릴 위치
        else sb.append(".");  // 빈 공간
    }
    canvas[currRow] = sb.toString();  // 완성된 행 저장
    currRow--;  // 다음 행으로 이동
}

6. 완성된 최소 사각형 반환

최소 격자 배열에 각 교점 위치에 별을 그린 결과를 반환합니다. 격자는 교점 좌표가 포함된 최소한의 크기로 생성되며, 각 행은 문자열로 구성되어 원하는 형식의 결과가 됩니다.

// 격자 반환
return canvas;

󰄉 Complexity

• ⏳ TC: O(N^2)
• 💾 SC: O(N)

모든 직선 쌍을 계산하므로, 최대 N^2 번의 교점 계산이 필요합니다. 각 교점은 정수 여부를 확인하고 좌표 범위를 갱신하는 연산을 포함하므로 이 복잡도는 입력 직선의 개수에 비례하여 증가합니다. 교점 좌표를 맵에 저장하고, 결과 격자를 생성하는 데 필요한 공간을 포함합니다.