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

문제 설명

 

 

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	result
[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]	["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]
[[0, 1, -1], [1, 0, -1], [1, 0, 1]]	["*.*"]
[[1, -1, 0], [2, -1, 0]]	["*"]
[[1, -1, 0], [2, -1, 0], [4, -1, 0]]	["*"]

 

---

 

코드 설명

 

 

문제에 주어진 공식에 따라 직선과 직선이 만나는 교점을 구합니다. 이때 x와 y 좌표는 실수형이므로 1.0으로 나누었을 때 나누어 떨어지는 즉, 정수 좌표만 구해 stars 배열에 저장합니다.

 

이후 x와 y의 최소-최대 범위를 구하고 해당 범위를 점으로 나타낸 배열 coord를 선언했습니다. 그리고 반복문을 통해 교점에 해당하는 점은 별로 바꾸어줍니다.

 

 

def solution(line):
    stars = []
    answer = []
    x_max = y_max = -int(1e15)
    x_min = y_min = int(1e15)
    
    # 교점 구하기
    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 % 1.0 == 0 and y % 1.0 == 0) :
                x = int(x)
                y = int(y)
                stars.append([x,y])
                # 교점이 있는 x와 y의 최소 범위 ~ 최대 범위 구하기
                if(x_min > x) : x_min = x
                if(y_min > y) : y_min = y
                if(x_max < x) : x_max = x
                if(y_max < y) : y_max = y
    
    # 해당 범위만큼 점 찍기
    x_len = x_max - x_min + 1
    y_len = y_max - y_min + 1
    coord = [['.'] * x_len for _ in range(y_len)]
    
    # 교점에 해당하는 점은 별로 바꾸기
    for star_x, star_y in stars :
        nx = star_x + abs(x_min) if x_min < 0 else star_x - x_min
        ny = star_y + abs(y_min) if y_min < 0 else star_y - y_min
        coord[ny][nx] = "*"
        
    for result in coord : answer.append(''.join(result))
    # answer을 거꾸로 리턴
    return answer[::-1]