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

문제

---

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

 

https://school.programmers.co.kr/learn/courses/30/lessons/87377

프로그래머스

 

문제 이해

---

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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

교점을 찾아 교점에 해당되는 영역을 그리면 되는 문제입니다.

 

알고리즘

---

1. Line으로 부터 주어진 교점 추출(못보고 수학식으로 풀었는데,,) 

2. 교점으로 부터 영역을 추출 ( x,y 최소 최댓값)

3. x,y최소 최댓값을 이용하여 그림 그리기

 

코드

---

# Programmers-교점에 별 만들기
import sys

# 교점
def intersect(a1,b1,c1,a2,b2,c2):
    if (a1*b2-a2*b1)==0 or (a2*b1-a1*b2)==0 or not ((b1*c2-b2*c1)/(a1*b2-a2*b1)).is_integer() or not ((a1*c2-a2*c1)/(a2*b1-a1*b2)).is_integer(): #or a1*b2-b1*c2==0:
        return False
    return (b1*c2-b2*c1) / (a1*b2-a2*b1) , (a1*c2-a2*c1)/(a2*b1-a1*b2)

def solution(line):
    answer = []
    intersect_list = set()
    #교점 경우의 수 추출
    for i in range(len(line)):
        for j in range(i+1,len(line)):
            temp = intersect(*tuple(line[i]+line[j]))
            if temp :
                intersect_list.add(tuple(map(int,temp)))

    # 추출된 값들 중 영역 확인
    max_x ,max_y,min_x,min_y = -sys.maxsize,-sys.maxsize ,sys.maxsize,sys.maxsize
    for a,b in intersect_list :
        max_x,max_y,min_x,min_y=max(max_x,a),max(max_y,b),min(min_x,a),min(min_y,b)
    
    for i in range(min_y,max_y+1):
        temp = ''
        for j in range(min_x,max_x+1) :
            if (j,i)in intersect_list :
                temp+='*'
            else:
                temp+='.'
        answer.append(temp)
    return answer[::-1]

#test
#solution([[0,1,-100],[1,0,-100]])
#solution([[0, 1, -1], [1, 0, -1], [1, 0, 1]])
#solution([[1, -1, 0], [2, -1, 0]])
#solution([[1, -1, 0], [2, -1, 0], [4, -1, 0]])