[알고리즘] 교점에 별 만들기

from itertools import combinations

def solution(line):
    
    lines = list(combinations(line, 2))
    dots = []
    for i in lines:
        a, b, e = i[0][0], i[0][1], i[0][2]
        c, d, f = i[1][0], i[1][1], i[1][2]
        if (a*d) - (b*c) == 0:
            continue
        x = ((b*f)-(e*d))/((a*d)-(b*c))
        y = ((e*c)-(a*f))/((a*d)-(b*c))
        dots.append([x,y])
    dots = [[int(x[0]), int(x[1])] for x in dots if float(x[0]).is_integer() if float(x[1]).is_integer()]
    
    if len(dots) == 0:
        return
    
    dots.sort(key = lambda x : x[0])
    max_x = int(dots[len(dots)-1][0])
    min_x = int(dots[0][0])
    len_x = abs(max_x - min_x)
    
    dots.sort(key = lambda x : x[1])
    max_y = int(dots[len(dots) - 1][1])
    min_y = int(dots[0][1])
    len_y = abs(max_y - min_y)
    
    answer = []
    for y in range(max_y, min_y - 1, -1):
        row = ""
        for x in range(min_x, max_x + 1):
            if [x, y] in dots:
                row += "*"
            else:
                row += "."
        answer.append(row)
        
    return answer
            

시간 복잡도나 공간 복잡도는 신경 쓰지 않았다.

구현에 더 집중한 문제이다.

흐름

1. 수학 공식을 이용하여 모든 교점을 구한다.
2. 리스트 컴프리헨션(조건부 집합)을 이용하여 모든 좌표가 정수인 교점만 남기고, 타입도 변경해준다.
3. 출력할 별들의 x 범위를 계산한다.
4. 출력할 별들의 y 범위를 계산한다.
5. 범위를 바탕으로 별과 점을 출력한다. 이때 출력할려는 점이 교점인 경우에만 별을 출력한다.
6. 교점이 0개인 엣지 케이스를 처리한다.