[프로그래머스] 교점에 별 만들기 - python

교점에 별 만들기

문제 설명

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

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

제한사항

• ine의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다.
  • line의 가로(열) 길이는 3입니다.
  • line의 각 원소는 [A, B, C] 형태입니다.
  • A, B, C는 -100,000 이상 100,000 이하인 정수입니다.
  • 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
  • A = 0이면서 B = 0인 경우는 주어지지 않습니다.
• 정답은 1,000 * 1,000 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

풀이

가능한 모든 조합 중 교점이 정수인 것만 골라서 집합에 넣는다.

width = abs(max_x - min_x) + 1

height = abs(max_y - min_y) + 1

교점을 y를 기준으로 내림차순으로 정렬하여 가장 높이 있는 것부터 출력한다.

미리 .으로 모든 좌표를 그려놓고 별 위치만 바꾸는 식으로 구현했다.

def solution(line):
    meet = set()
    max_x, max_y = -float('inf'), -float('inf')
    min_x, min_y = float('inf'), float('inf')
    
    for i in range(len(line)):
        a, b, e = line[i]
        for j in range(i + 1, len(line)):
            c, d, f = line[j]
            if ((a * d) - (b * c)) != 0:
                x = ((b * f) - (e * d)) / ((a * d) - (b * c))
                y = ((e * c) - (a * f)) / ((a * d) - (b * c))
                if x.is_integer() and y.is_integer():
                    meet.add((int(x), int(y)))
                    max_x, max_y = max(max_x, int(x)), max(max_y, int(y))
                    min_x, min_y = min(min_x, int(x)), min(min_y, int(y))
    
    meet = sorted(list(meet), key=lambda x:-x[1])
    width = abs(max_x - min_x) + 1
    height = abs(max_y - min_y) + 1
    
    answer = [["."] * width for _ in range(height)]
    
    for x, y in meet:
        idx_y = max_y - y
        idx_x = x - min_x
        answer[idx_y][idx_x] = "*"
    
    
    return list(map("".join, answer))

처음에는 최대 값을 0으로 초기화했다가 테스트케이스 하나가 틀렸었는데 -무한대로 초기화하니까 통과했다.

초기화는 확실한 값으로 할 것..!