[프로그래머스] Lv 2. 교점에 별 만들기

코딩테스트 연습 - 교점에 별 만들기

 

문제

Ax+By+C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.

 

직선 A,B,C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다.

이 때 모든 별을 포함하는 최소 사각형을 return하도록 solution 함수를 완성해주세요.

 

풀이

다행히 문제에서 교점을 구하는 공식이 주어집니다.😊👍

이를 모르고 공식 구하려다 시간이 더 걸렸습니다.ㅎㅎ😭

1. 먼저 각 직선들의 교점을 구해보겠습니다. 직선의 개수가 많지 않으니 2중 for문을 이용해 구할 수 있습니다.

for i in range(0, len(line)-1):
	for j in range(i+1, len(line)):
    	able, x, y = getCrossPos(line[i], line[j])
        # 교점이 있고, 정수인 경우에만 answer에 추가
        if able and x == int(x) and y == int(y):
        	answer.append(int(x), int(y))

교점을 구하는 함수인 getCrossPos는 문제에 주어진 공식을 이용해 구현할 수 있습니다.

🔥 이 때, zero divide 처리를 해주어야 합니다.

 

2. 교점들을 모두 구했다면, 이제 화면에 출력할 좌표의 크기를 구해보겠습니다.

가로 길이는 최대 x좌표 - 최소 x좌표 + 1

세로 길이는 마찬가지로 최대 y좌표 - 최소 y좌표 + 1 입니다.

minx = min(answer, key=lambda x: x[0])[0]
maxx = max(answer, key=lambda x: x[0])[0]
miny = min(answer, key=lambda x: x[1])[1]
maxy = max(answer, key=lambda x: x[1])[1]
    
width = maxx - minx + 1 # 너비
height = maxy - miny + 1 # 높이

maps = [['.']*width for _ in range(height)]

이제 만들어진 사각형에 교점마다 별을 찍어주면 완성입니다.😊

 

코드

def solution(line):
    answer = []
    
    for i in range(0, len(line)-1):
        for j in range(i+1, len(line)):
            able, x, y = getCrossPos(line[i], line[j])
            if able and x == int(x) and y == int(y):
                answer.append((int(x), int(y)))
    
    minx = min(answer, key=lambda x: x[0])[0]
    maxx = max(answer, key=lambda x: x[0])[0]
    miny = min(answer, key=lambda x: x[1])[1]
    maxy = max(answer, key=lambda x: x[1])[1]
    
    width = maxx - minx + 1
    height = maxy - miny + 1
    
    maps = [['.']*width for _ in range(height)]
    for x, y in answer:
        maps[(y-maxy)*-1][x-minx] = '*'
    
    result = []
    for m in maps:
        result.append(''.join(m))
    
    return result

def getCrossPos (a, b):
    aa, ab, ac = a
    ba, bb, bc = b
    
    ax = (ab*bc-ac*bb)
    bx = (aa*bb-ab*ba)
    ay = (ac*ba-aa*bc)
    by = (aa*bb-ab*ba)
    
    if bx == 0 or by == 0:
        return False, 0, 0
    
    x = ax / bx
    y = ay / by
    return True, x, y