교점에 별 만들기

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

---

입출력 예

lineresult

[[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]]	["*"]

 

코딩테스트 연습 - 교점에 별 만들기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 풀이

# 2024-08-07
from itertools import combinations
def solution(line):
    answer = []
    
    point_set = set()
    
    max_x, min_x = -float('inf'), float('inf')
    max_y, min_y = -float('inf'), float('inf')
    
    for line1, line2 in combinations(line, 2):
        momo=(line1[0]*line2[1]-line1[1]*line2[0])
        if momo:
            x=(line1[1]*line2[2]-line1[2]*line2[1])/momo
            y=(line1[2]*line2[0]-line1[0]*line2[2])/momo
            if int(x)==x and int(y)==y:
                max_x = max(max_x, int(x))
                min_x = min(min_x, int(x))
                max_y = max(max_y, int(y))
                min_y = min(min_y, int(y))
                point_set.add((x,y))

    
    star = []
    for _ in range(min_y, max_y+1):
        star_list = []
        for x_ct in range(min_x, max_x+1):
            star_list.append('.')
        star.append(star_list)

    for x,y in point_set:
        ch_x = int(x) - min_x
        ch_y = max_y - int(y)

        star[ch_y][ch_x]='*'
    for i in star:
        answer.append(''.join(i))

    return answer

 

시간 복잡도

for x1, x2 in combinations(line, 2) : 입력변수 line 모든 쌍을 조회하므로 이차형 시간복잡도
star = [['.'] * x_range for _ in range(y_range)] : 별 리스트 생성 이차형 시간복잡도
for x, y in command_point : 별 표시 선형 시간복잡도
for i in star : 별 answer에 append 선형 시간복잡도

즉, 해당 알고리즘은 이차형 시간복잡도를 가짐