교점에 별 만들기(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

직선간 모든 교점을 구해야하기 때문에 이중 for문을 돌면서 두 직선의 교점을 모두 구해준다. 그리고 모든 별을 포함하는 최소한의 크기만 나타내야하기 때문에 교점의 가장 끝에 존재하는 상,하,좌,우의 좌표를 구해서 해당 크기 만큼의 영역을 만들어준 후, 별을 그려주는 방식으로 문제를 풀었다. 

 

이때 교점을 구하는 방식은 아래와 같다.

 

 

시간 복잡도

모든 직선에 대해 두 직선 간 교점을 구해야하기 때문에 이중 for문을 돌아야해서 O(n^2)이 걸리며 직선의 최대 개수가 1000이기 때문에 시간내에 동작한다.

 

 

코드

INF = int(1e18)
def solution(line):
    
    # 1. 직선 간 교점을 구해서 리스트에 넣는다.
    # 이때, l,t,r,b 끝점을 계속 갱신한다
    left=bottom=INF
    right=top=-INF
    n=len(line)
    points=set()
    
    for i in range(n):
        a,b,e=line[i]
        for j in range(i+1,n):
            c,d,f=line[j]
            under=a*d-b*c
            if under==0:
                continue
            if (b*f-e*d)%under==0 and (e*c-a*f)%under==0:
                y=(e*c-a*f)//under
                x=(b*f-e*d)//under
                points.add((y,x))
                
                
    # x,y 최대,최소 구하기
    x_list = []
    y_list = []
    for y,x in list(points):
        x_list.append(x)
        y_list.append(y)
    
    right = max(x_list) 
    left = min(x_list)
    top = max(y_list)
    bottom = min(y_list)
    
    w,h=right-left+1,top-bottom+1
    
    board = [['.']*w for _ in range(h)]
    
    for y,x in points:
        board[top-y][x-left]='*'
    
    answer=[]
    for row in board:
        answer.append(''.join(row))
        
    return answer

 

 

회고

초기에 아래와 같이 교점의 최댓값, 최솟값을  1e9, -1e9로 설정하고 풀었는데 에러가 났다. 교점의 범위가 없었지만 int 형 내에서 주어지겠지라고 막연하게 생각하고 풀었는데 2개의 케이스에서 시간초과가 떴고, 어디서 문제가 발생한지 몰라서 다른 사람 풀이를 참고했다. 에러가 발생하는 이유는 교점이 int 범위보다 큰 경우도 주어지며 이럴 경우 INF가 제대로 동작하지 않는다.

INF = int(1e9)

left=bottom=INF
right=top=-INF

bottom,left=min(bottom,y),min(left,x)
top,right=max(top,y),max(right,x)

 

 

위의 코드에서 INF의 범위를 long long 에 해당하는 값까지 높여줘야하며, int(1e18) 로 변경하면 제대로 동작한다. 하지만, 문제에서 애초에 교점의 범위를 주어주지 않았기 때문에 교점들에 대해 min,max를 사용해서 최대,최솟값을 구하는게 합리적인 방법으로 보인다

# x,y 최대,최소 구하기
x_list = []
y_list = []
for y,x in list(points):
    x_list.append(x)
    y_list.append(y)

right = max(x_list) 
left = min(x_list)
top = max(y_list)
bottom = min(y_list)