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

문제

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

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

 

입출력 예

 

---

되게 쉬운 문자열 처리 문제 같은데,

생각보다는 고려해야 될 점이 몇가지 있다.

 

참고 사항이 없었으면 어려웠겠지만.. 있어서 그래도 간단하게 풀 수 있었다.

ㅜㅜ

 

생각했던 아이디어는 다음과 같다.:

- 입력받은 선 끼리의 모든 조합을 통해 교점을 계산해준다.

- 직선이 서로 평행하거나 일치하여 기울기가 0인 경우를 제외하고 교점을 계산해주되,

   교점의 좌표가 정수인 경우에만 좌표 배열에 좌표 정보를 추가한다.

for i in range(len(line)):
    for j in range(i + 1, len(line)):
        if incline(line[i], line[j]) == 0:
            continue
        else:
            x, y = cross(line[i], line[j])
            
            if(x == int(x) and y == int(y)):
                coord.append([x, y])

- 좌표 배열로부터 최대/최소 바운더리를 한정해주기 위해 x, y 각각 최댓값과 최솟값을 저장해둔다.

- 최대최소 바운더리만큼 '.' 만 담긴 temp 배열을 선언해주고,

   교점이 들어가는 위치에는 '*'로 바꿔준다.

 

이때 중요한 작업은

입력받은 좌표계와 컴퓨터 배열의 위치를 일치시켜주는 것이다.

for i in coord:
    temp[y_max - int(i[1])][int(i[0]) - x_min] = '*'

 

 

이렇게 바꿔준 후,

answer 배열에 join을 통해 문자열로 변환해주면 끝!!

for i in range(len(temp)):
    answer[i] = ''.join(temp[i])

 

 

코드

def incline(line1, line2):
    inc = (line1[0] * line2[1] - line1[1] * line2[0])
    return inc

def cross(line1, line2):
    x = (line1[1] * line2[2] - line1[2] * line2[1])
    y = (line1[2] * line2[0] - line1[0] * line2[2])
    inc = incline(line1, line2)

    return [x / inc, y / inc]

def solution(line):
    coord = []

    for i in range(len(line)):
        for j in range(i + 1, len(line)):
            if incline(line[i], line[j]) == 0:
                continue
            else:
                x, y = cross(line[i], line[j])
                
                if(x == int(x) and y == int(y)):
                    coord.append([x, y])
    
    x_list = [i[0] for i in coord]
    y_list = [i[1] for i in coord]

    x_min = int(min(x_list))
    x_max = int(max(x_list))
    y_min = int(min(y_list))
    y_max = int(max(y_list))

    temp = [['.'] * (x_max - x_min + 1) for _ in range(y_max - y_min + 1)]

    for i in coord:
        temp[y_max - int(i[1])][int(i[0]) - x_min] = '*'

    answer = ['' for _ in range(y_max - y_min + 1)]
    for i in range(len(temp)):
        answer[i] = ''.join(temp[i])
        
    return answer