문제 링크

문제 간단 해석

직선들의 교점을 찾아 정리한 후 해당 교점들을 모두 포함할 수 있는 크기만큼만 출력하는 문제.
알고리즘상 어렵진 않으나 자료형 이슈가 있었다.

Java

자료형을 잘못 작성한다면 한참 헤멜 수 있다.

풀이 코드

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    
    class Star {
        private long y;
        private long x;

        public Star(long y, long x) {
            this.y = y;
            this.x = x;
        }

        public long getY() {
            return y;
        }

        public long getX() {
            return x;
        }
        
        public String toString() {
            return "(" + y + ", " + x + ")";
        }
    }
    
    public String[] solution(int[][] line) {
        double A, B, C, D, E, F, yf, xf;
        long y, x, max_y = Long.MIN_VALUE, max_x = Long.MIN_VALUE, min_y = Long.MAX_VALUE, min_x = Long.MAX_VALUE;
        List<Star> stars = new ArrayList<>();
        
        for (int i = 0; i < line.length - 1; i++) {
            A = line[i][0];
            B = line[i][1];
            E = line[i][2];
            
            for (int j = i + 1; j < line.length; j++) {
                C = line[j][0];
                D = line[j][1];
                F = line[j][2];
                
                xf = (B * F - E * D) / (A * D - B * C);
                yf = (E * C - A * F) / (A * D - B * C);
                
                if (!(yf % 1 == 0 && xf % 1 == 0))
                    continue;
                
                y = (long) yf;
                x = (long) xf;
                
                max_y = Math.max(y, max_y);
                max_x = Math.max(x, max_x);
                min_y = Math.min(y, min_y);
                min_x = Math.min(x, min_x);
                    
                stars.add(new Star(y, x));
            }
        }
        
        char[][] field = new char[(int)(max_y - min_y) + 1][(int)(max_x - min_x) + 1];
        
        for (int i = 0; i < field.length; i++)
            Arrays.fill(field[i], '.');
        
        for (Star star: stars)
            field[(int)(star.getY() - min_y)][(int)(star.getX() - min_x)] = '*';
        
        String[] answer = new String[field.length];
        
        for (int i = 0; i < field.length; i++)
            answer[field.length - i - 1] = new String(field[i]);
        
        return answer;
    }
}

해석

Star 해석 스킵. (toString()은 디버그하려고 구현, 없어도 무방)

double A, B, C, D, E, F, yf, xf;
long y, x, max_y = Long.MIN_VALUE, max_x = Long.MIN_VALUE, min_y = Long.MAX_VALUE, min_x = Long.MAX_VALUE;

문제 조건 중 A, B, C는 -100,000 이상 100,000 이하인 정수가 있는데, 교점의 최댓값을 예측하자면 대략 100,000,000,000 (천억) 가까이 나온다. float, int형으로는 소화할 수 없음. 따라서 double, long으로 선언했다. (float 그대로 두고 풀면 29번만 틀리더라. 한참 찾았음)

for (int i = 0; i < line.length - 1; i++) {
    A = line[i][0];
    B = line[i][1];
    E = line[i][2];
    
    for (int j = i + 1; j < line.length; j++) {
        C = line[j][0];
        D = line[j][1];
        F = line[j][2];
        
        xf = (B * F - E * D) / (A * D - B * C);
        yf = (E * C - A * F) / (A * D - B * C);

하나씩 가져와서 교점 계산. 참고 사항 제대로 안읽고 A, B, C로 선언 후 돌렸다가 교점이 죄다 이상하게 나왔었다. 잘 확인할 것.

if (!(yf % 1 == 0 && xf % 1 == 0))
    continue;

y = (long) yf;
x = (long) xf;

max_y = Math.max(y, max_y);
max_x = Math.max(x, max_x);
min_y = Math.min(y, min_y);
min_x = Math.min(x, min_x);
    
stars.add(new Star(y, x));

yf, xf가 소수점이 있다면 스킵. 없으면 long으로 형변환하고 최대, 최소를 갱신. 그 후 리스트에 넣는다.

char[][] field = new char[(int)(max_y - min_y) + 1][(int)(max_x - min_x) + 1];

for (int i = 0; i < field.length; i++)
    Arrays.fill(field[i], '.');

for (Star star: stars)
    field[(int)(star.getY() - min_y)][(int)(star.getX() - min_x)] = '*';

String[] answer = new String[field.length];

for (int i = 0; i < field.length; i++)
    answer[field.length - i - 1] = new String(field[i]);

return answer;

char 이차원 배열 만들고 최대 - 최소로 배열의 크기를 정한다.
배열 내 값을 다 .으로 초기화 후 stars 리스트에서 하나씩 값을 뽑아 해당 자리를 *로 만든다.
그 후 한줄씩 뽑아 String으로 만들고 반환. 이 때, 배열의 y좌표값과 그림의 y좌표값은 증감이 반대이므로 거꾸로 넣어준다.

Python

풀이 코드

def solution(line):
    stars = set()
    
    for i in range(len(line) - 1):
        for j in range(i + 1, len(line)):
            A, B, E = line[i]
            C, D, F = line[j]
            if A * D - B * C:
                y = (E * C - A * F) / (A * D - B * C)
                x = (B * F - E * D) / (A * D - B * C)
                if not y % 1 and not x % 1:
                    y = int(y)
                    x = int(x)
                    
                    stars.add((y, x))
    
    stars = list(stars)
    max_y, max_x = stars[0]
    min_y, min_x = stars[0]
    
    for y, x in stars:
        if max_y < y:
            max_y = y
        if min_y > y:
            min_y = y
        if max_x < x:
            max_x = x
        if min_x > x:
            min_x = x

    row = max_y - min_y + 1
    col = max_x - min_x + 1
    
    sky = [['.'] * col for _ in range(row)]
    for y, x in stars:
        y -= max_y
        x -= min_x
        sky[-y][x] = '*'
    
    return [''.join(s) for s in sky]

해석

stars = set()

for i in range(len(line) - 1):
    for j in range(i + 1, len(line)):
        A, B, E = line[i]
        C, D, F = line[j]
        if A * D - B * C:
            y = (E * C - A * F) / (A * D - B * C)
            x = (B * F - E * D) / (A * D - B * C)
            if not y % 1 and not x % 1:
                y = int(y)
                x = int(x)
                
                stars.add((y, x))

교점을 구하고, 정수형으로 나타낼 수 있으면 set에 추가시킨다. (Java도 set 쓸걸.. 생각을 못했네)

for y, x in stars:
    if max_y < y:
        max_y = y
    if min_y > y:
        min_y = y
    if max_x < x:
        max_x = x
    if min_x > x:
        min_x = x

row = max_y - min_y + 1
col = max_x - min_x + 1

sky = [['.'] * col for _ in range(row)]
for y, x in stars:
    y -= max_y
    x -= min_x
    sky[-y][x] = '*'

return [''.join(s) for s in sky]

최대, 최소 갱신
최적 좌표 크기 구함
.으로 초기화하고, 처음부터 y방향 역좌표 계산해서 * 넣어준다.
그 후 join으로 문자열 만들고 반환.