풀이_교점에별만들기.md

🏭 프로그래머스 교점에 별 만들기

• Date : 2021.01.09(일)
• Time : 40분

문제 설명

• Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다. 예를 들어, 다음과 같은 직선 5개를 좌표 평면 위에 그리면 아래 그림과 같습니다.

  2x - y + 4 = 0
  -2x - y + 4 = 0
  -y + 1 = 0
  5x - 8y - 12 = 0
  5x + 8y + 12 = 0
  

• 이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)입니다. 위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다. 직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

제한 사항

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

예시

• line : [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]
• result : ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]

풀이

from itertools import combinations

def intersection_point(line1, line2):
    a,b,e = line1
    c,d,f = line2
    if a*d == b*c:
        return None
    x = (b*f-e*d)/(a*d-b*c)
    y = (e*c-a*f)/(a*d-b*c)
    if x == int(x) and y == int(y):
        return (int(x),int(y))
    
def solution(line):
    N = len(line)
    
    combs = list(combinations(line,2))
    points = set()
    for comb in combs:
        point = intersection_point(comb[0], comb[1])
        if point:
            points.add(point)
            
    xs = [p[0] for p in points]
    x_min = min(xs)
    x_max = max(xs)
    
    ys = [p[1] for p in points]
    y_min = min(ys)
    y_max = max(ys)
    
    answer = ['.' * (x_max-x_min+1)] * (y_max-y_min+1)
    for point in points:
        x,y = point
        answer[y_max-y] = answer[y_max-y][:x-x_min] + '*' + answer[y_max-y][x-x_min+1:]
        
    return [''.join(ans) for ans in answer]

: 문제에 제시된 참고사항을 참고해 두 직선의 모든 좌표가 정수인 교점을 구하는 함수 intersection_point를 만들어주었다. solution 함수에선 입력으로 주어진 모든 직선을 2개씩 짝지어 교점을 구하고, 이들을 points라는 집합에 먼저 저장하였다. 각 교점의 x좌표의 최대, 최솟값과 y좌표의 최대, 최솟값을 구해 최종 반환값의 크기를 파악하는 과정이 필요하다. 이 크기에 맞게 우선 . 으로 초기화하고, 각 점을 하나씩 확인하면서 해당하는 위치에 *을 그려주었다.