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

---

입출력 예

입력 예시	출력 예시
[[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]]	["*"]

 

참고 사항

Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.

---

풀이

 

문제를 끝까지 안 읽고 참고사항을 놓쳤다. 몽총이짓 다음에는 하지 말자.

def solution(line):
    '''
    line: 직선 Ax + By + C = 0 에 대한 정보가 담긴 배열 
    idea: 1. 교점 구하기 2. *로 print하기
    '''
    meet = [] # 교점의 좌표 담는 list
    for a,b,c in line:
        for d,e,f in line:
            if not (a==d and b==e and c==f) and (a*e != b*d): # 교점이 있는 경우
                x = (b*f-c*e) / (a*e-b*d) # 나누어 떨어져야 함
                y = (c*d-a*f) / (a*e-b*d)
                if (x == int(x) and y== int(y)) and [x,y] not in meet:
                    meet.append([int(x), int(y)]) # 나누면 float
                    
    x_min = min(meet)[0]
    x_max = max(meet)[0] # min(meet)[-1]
    y_min = min(meet, key = lambda x: x[1])[1]
    y_max = max(meet, key = lambda x: x[1])[1] #min(meet, key = lambda x: x[1])[-1]
    
    # 1. .으로 기본 좌표계(2차원 arr) 생성  2. *를 찍기
    coordinate = [['.']*(x_max-x_min+1) for _ in range(y_max - y_min+1)]
    for dot in meet:
        x, y = dot # 일반 좌표에서의 x,y 좌표
        new_x, new_y = abs(y_max -y), abs(x- x_min) 
        coordinate[new_x][new_y] = '*'
    
    answer = []
    for c in coordinate:
        answer.append(''.join(c))
    '''
    for i,v in enumerate(coordinate):
        star[i] = ''.join(v)
    '''
    return answer

주의 : 행은 y 값을 기준으로, 열은 x 값을 기준으로 계산

---

📝

int와 float형인데 값이 동일한 지 비교가 가능한 이유 (산술연산이 가능한 이유)

 int형과 float형의 비교연산시에는 두 자료형의 eq메소드를 호출하게 되는데,
int형의 메소드는 float형과의 비교를 지원하지 않지만, float형의 메소드는 int형과의 비교가 가능하다.

그래서 float의 메소드를 사용하여 에러가 발생하지 않고 비교연산이 가능하다.

 

_번째 값을 기준으로 정렬하기

arr = [[1,2],[2,1],[3,1],[3,4],[4,1]]
print(min(arr)) #[1, 2]
print(max(arr)) #[4, 1]

arr.sort(key=lambda x: x[1]) 
# [[2, 1], [3, 1], [4, 1], [1, 2], [3, 4]] 두번째 값 기준 정렬
print(arr[0][1]) # y의 최솟값
print(arr[-1][1]) # y의 최댓값

---

다른 풀이

idea: itertools의 combinations을 사용하여 직선 두 개씩 모든 쌍의 경우의 수를 구함

def solution(line):
    
    def cross_at(line1, line2):
        '''교점의 x,y 좌표'''
        a, b, e = line1
        c, d, f = line2
        denom = (a*d - b*c)
        if denom == 0:
            # 서로 접점이 없으면 패스
            return False
        x, y = (b*f - e*d) / denom , (e*c-a*f) /denom
        if int(x) != x or int(y) != y:
            # 정수가 아니면 패스
            return False
        return (int(x),int(y))
    
    def draw(coordinates):
        x_min, x_max, y_min, y_max = float("inf"), -float("inf"), float("inf"), -float("inf")
        for coord in coordinates:
            x_min, x_max = min(x_min, coord[0]), max(x_max, coord[0])
            y_min, y_max = min(y_min, coord[1]), max(y_max, coord[1])
        
        palette = [["."] * (x_max-x_min+1) for _ in range(y_max-y_min+1)]
        for coord in coordinates:
            x, y = coord
            dist_x, dist_y = x-x_min, y_max-y
            palette[dist_y][dist_x] = "*" 

        return palette
        
    from itertools  import combinations
    combns = combinations(range(len(line)), 2)
    answer = []
    for l1, l2 in combns:
        coord = cross_at(line[l1], line[l2])
        if not coord:
            # 교점이 없으면
            continue
        answer.append(coord)
    answer = draw(answer)        
    answer = [''.join(row) for row in answer]
        
    return answer