[Python] 교점에 별 만들기

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

프로그래머스

 

분석

• Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표
• 모든 별을 포함하는 최소 사각형을 return

Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.
X= (BF - ED) / (AD - BC)
y = (EC - AF) / (AD - BC)

 

 

. . . . . . . . . . .
. . . . . * . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. * . . . . . . . * .
. . . . . . . . . . . 
. . . . . . . . . . . 
. . . . . . . . . . . 
. . . . . . . . . . . 
. * . . . . . . . * .
. . . . . . . . . . .

 

 

1. 모든 직선을 두개 뽑아 교점 구하기
   1. 기울기가 같으면 평행하기 때문에 교점 없음
   2. 두 직선의 해 구하기  
      1. x = (y1*c2-c1*y2)/(x1*y2-y1*x2)
      2. y = (c1*x2-x1*c2)/(x1*y2-y1*x2)
   3. 교점이 정수인 경우 points 배열에 추가
2.  최소 사각형 그리기
   1. 교점 배열의 각 교점 x,y의 최댓값, 최솟값 구하기
   2. 사각형 가로 길이 : x최댓값 - x최솟값 / 사각형 세로 길이 : y최댓값 - y최솟값
   3. 교점 배열 돌면서 별 찍기
3. 사각형 행 뒤집기 ( 배열의 행과 좌표의 행 맞추기 위해)
4. 한줄씩 string으로 묶어서 리턴

 

풀이

from itertools import combinations
def solution(line):
    
    points=[] # 교점
    for l1, l2 in combinations(line,2):
        x1, y1, c1 = l1 # 직선1
        x2, y2, c2 = l2 # 직선2

        if x1*y2 != y1*x2: # 기울기 다름
            # 두 직선의 해
            x = (y1*c2-c1*y2)/(x1*y2-y1*x2)
            y = (c1*x2-x1*c2)/(x1*y2-y1*x2)

            # 두 직선의 해 x, y가 모두 정수라면 반환
            if x == int(x) and y == int(y):
                points.append([int(x), int(y)])
    
    
    ws,we = min(points, key = lambda x : x[0])[0], max(points, key = lambda x : x[0])[0]+1
    hs,he = min(points, key = lambda x : x[1])[1], max(points, key = lambda x : x[1])[1]+1
    
    # 모든 별을 포함하는 최소 사각형 배열
    answer = [['.']*(we-ws) for _ in range(he-hs)]
    for x, y in points:
        answer[y-hs][x-ws] = '*'
    answer.reverse()
    

    return [''.join(i) for i in answer]