Level 2 교점에 별 만들기 Python 3

https://programmers.co.kr/learn/courses/30/lessons/87377?language=python3 

코딩테스트 연습 - 교점에 별 만들기

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_교점에별만들기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def solution(line):
    point_x = []
    point_y = []
    for i in range(len(line)-1):
        for j in range(i+1, len(line)):
            a1, b1, c1 = line[i]
            a2, b2, c2 = line[j]
            if a1*b2 - a2*b1 == 0: continue
            x = (b1*c2-b2*c1)/(a1*b2-a2*b1)
            y = (a2*c1-a1*c2)/(a1*b2-b1*a2)
            if x.is_integer() and y.is_integer():
                x = int(x)
                y = int(y)
                point_x.append(int(x))
                point_y.append(int(y))

    min_x, min_y = min(point_x), min(point_y)
    board = [['.']*(max(point_x)-min_x+1) for _ in range(max(point_y)-min_y+1)]
    
    for x, y in zip(point_x, point_y):
        ny = y-min_y
        nx = x-min_x
        board[ny][nx] = '*'
    
    answer = []
    for i in range(len(board)-1, -1, -1):
        answer.append("".join(board[i]))
        
    return answer

---

풀이 과정

풀이 시간 54분

def solution(line):
	#교점의 좌표들을 담는 배열
    point_x = []
    point_y = []
    
    #두 직선의 교점 찾기
    for i in range(len(line)-1):
        for j in range(i+1, len(line)):
            a1, b1, c1 = line[i]
            a2, b2, c2 = line[j]
            
            #두 직선이 평행한 경우, 교점이 존재하지 않는다
            if a1*b2 - a2*b1 == 0: continue
            
            #교점 (x, y)
            x = (b1*c2-b2*c1)/(a1*b2-a2*b1)
            y = (a2*c1-a1*c2)/(a1*b2-b1*a2)
            
            #x와 y가 정수인 경우, 배열에 저장한다
            if x.is_integer() and y.is_integer():
                x = int(x)
                y = int(y)
                point_x.append(int(x))
                point_y.append(int(y))

	#모든 교점을 포함하는 사각형 그리기
    min_x, min_y = min(point_x), min(point_y)
    board = [['.']*(max(point_x)-min_x+1) for _ in range(max(point_y)-min_y+1)]
    
    for x, y in zip(point_x, point_y):
        ny = y-min_y
        nx = x-min_x
        board[ny][nx] = '*'
    
    #y좌표는 반대로 그려지므로 뒤에서부터 차례대로 정답 배열에 담는다
    answer = []
    for i in range(len(board)-1, -1, -1):
        answer.append("".join(board[i]))
        
    return answer
    
#시간복잡도 = O(n!), 공간복잡도 = O(n)