[프로그래머스 Lv2] 교점에 별 만들기 (파이썬)

문제 링크

문제 설명

Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리는 함수 작성

풀이 코드

from itertools import combinations


# 교점 좌표를 반환하는 함수
def cross_point(first, second):
    x1, y1, b1 = first
    x2, y2, b2 = second
    disc = x1 * y2 - y1 * x2
    if disc != 0:
        x = (y1 * b2 - y2 * b1) / disc
        y = (x2 * b1 - x1 * b2) / disc
        if x == int(x) and y == int(y):
            return int(x), int(y)
        else:
            return None
    else:
        return None    
        

def solution(line):
    cross = list(set(cross_point(a, b) for a, b in combinations(line, 2) if cross_point(a, b) is not None))
    # x, y의 최대값 최소값을 구하여 배열 길이와 좌표를 설정하기 위한 과정
    xs = [x for x, _ in cross]
    ys = [y for _, y in cross]
    max_x, min_x = max(xs), min(xs)
    max_y, min_y = max(ys), min(ys)
    
    # 문자열 핸들링 전 반환할 문자열배열 기본값 설정
    answer = ["." * (max_x - min_x + 1)] * (max_y - min_y + 1)
    
    for x, y in cross:
        # 좌표평면 상의 좌표를 인덱스로 변환
        y = max_y - y
        x = x - min_x
        
        # 문자열 핸들링
        answer[y] = answer[y][:x] + "*" + answer[y][x+1:]
    return answer

코드 설명

0. 수학적 접근이 필요했던 문제로, 중고등학교 수준이지만 너무 오래돼서 기억이 안나 한참을 헤메다가 수학의 정석을 다시 펼쳐서 풀었던 문제
1. combinations 모듈을 활용하여 주어진 n개의 방정식 중 2개를 조합하는 배열을 생성하되, 교점의 좌표가 존재할 때를 찾아야하므로 교점 좌표를 반환하는 별도의 함수 작성
2. 위 1번을 해결하기 위해 유리함수 판별식(discriminant; 또는 행렬식)을 활용하여, 판별식이 0이 아닐 때(해가 존재할 때) x와 y의 값을 반환하도록 작성
3. 2번에서 작성한 함수의 반환값이 None이 아닐 경우에만 교점의 좌표를 담는 list comprehension 작성
4. 이후 좌표평면 상의 개념을 배열로 옮기기 위하여 x, y 각각의 최대/최소값을 구하고, 이를 활용하여 인덱스화를 진행
5. 정답으로 반환할 기본 문자열 초기값을 "."으로 설정한 뒤 각 교점 좌표마다 문자열 슬라이싱을 활용하여 "*"로 변환