[위클리 챌린지 / 프로그래머스] 87377번 : 교점에 별 만들기

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

 

문제 이해

• 교점을 구하는 두직선은 조합을 통해서 임의로 진행한다. 
• 두 직선의 교점이 있다면 찾는 find_intersection_point()를 실행한다
  
  • 평행하거나 일치하는 선분은 건너뛰고, 기울기가 다른 선분들에 대해서 진행한다.
  • 교점이 있고, 좌표가 모두 정수라면 튜플 형태로 반환한다.
  • 튜플로 반환하는 이유는 교점이 중복될 수 있으므로 중복을 없애기 위해 set()을 이용할 건데, 그러기 위해선 원소들을 튜플로 해야하기 때문이다. ([]를 set에 넣으면 에러난다)
• 임의의 두 선분에 정수인 교점이 존재한다면 points에 추가하고, 교점의 x좌표, y좌표를 따로 x_points, y_points에 추가한다.
• x좌표와 y좌표의 최소, 최댓값을 구하기 위해서 x_points, y_points를 사용한다.
• 가로 세로의 최대 ~ 최소 값으로 2차 행렬을 만든다. 
• 행은 좌표에서 y값, 열은 좌표에서 x값이므로 교점 (x,y)에 대해서 [y_max - y][x - x_min] 위치 값을 '*'로 바꿔준다.
• 각 행렬을 문자열로 바꿔서 반환한다. 

 

- 정답 풀이 : 

 

문제 중 여기가 가장 안됐는데, 행렬의 인덱스와 좌표 구조가 달라서 어떻게 할지 몰랐다. 

x_max/min, y_max/min 모두 좌표값이므로 (x,y)에서 x는 x_min로부터 x만큼 오른쪽으로 더 갔고, y는 y_max로부터 y만큼 줄어든 위치에 있다. (이부분은 나중에 그림 추가할 예정) 

 	for x, y in points:
        answer[y_max - y][x - x_min] = '*'  # 교점에 별 만들기
        
    return list(map(''.join, answer))

 

 

참고한 블로그

from itertools import combinations


def find_intersection_point(line1, line2):  # 두 직선의 모든 좌표가 정수인 교점 구하기
    a, b, e = line1  # ax + by + e = 0
    c, d, f = line2  # cx + dy + f = 0
    if a * d == b * c:  # 기울기가 일치하거나 평행인 경우
        return
    x = (b * f - e * d) / (a * d - b * c)
    y = (e * c - a * f) / (a * d - b * c)
    if x == int(x) and y == int(y):  # 교점이 정수라면
        return (int(x), int(y))


def solution(line):
    points = set()  # 교점
    x_points, y_points = set(), set()  # x_points : 교점의 x좌표들, y_points : 교점의 y좌표들
    for a, b in combinations(line, 2):  # 선분들 중 2개 골라서
        point = find_intersection_point(a, b)
        if point:  # 교점이 존재한다면
            points.add(point)
            x_points.add(point[0])
            y_points.add(point[1])

    x_min, x_max = min(x_points), max(x_points)  # 교점의 x좌표들 중 최소값과 최대값
    y_min, y_max = min(y_points), max(y_points)  # 교점의 y좌표들 중 최소값과 최대값

    answer = [['.'] * (x_max - x_min + 1) for _ in range(y_max - y_min + 1)]
    for x, y in points:
        answer[y_max - y][x - x_min] = '*'  # 교점에 별 만들기
    return list(map(''.join, answer))

 

- 시도해본 풀이 :

 

직선의 형태가 각각 3개씩이라 총 9가지 경우라서 모두 직접 구현했다. (기울기 있는 경우, x = c 인경우, y = c인 경우) -> 이렇게 하면 안된다

각 상황에서 정수인 교점을 모두 구해서 intersect에 저장한 다음 그 중에서 최대 행, 최소 행을 이용해 총 행의 수를 구하고 최대 열, 최소 열을 이용해 총 열의 수를 구한다.

그다음 좌표들 위치에 하나씩 *를 찍는데, 좌표를 어떻게 행렬로 옮겨야할지 모르겠어서 걸렸던 문제다. 

def check(x,y):
    if float(x).is_integer() and float(y).is_integer():
        return True
    return False

def solution(line):
    intersect = []
    
    for i in range(len(line)):
        for j in range(i + 1, len(line)):
            x1, y1, c1 = line[i]
            x2, y2, c2 = line[j]
            # 기울기 있는 직선
            if x1 != 0 and y1 != 0:
                if x2 != 0 and y2 != 0 :
                    y1, c1 = y1 / (-1 * x1), c1/ (-1 * x1) #x의 계수로 나눔 
                    y2, c2 = y2 / (-1 * x2), c2 / (-1 * x2)
                    tempy, tempc = y1 - y2, c2 - c1
                    y = tempc / tempy
                    x = y1 * y + c1
                if x2 == 0 and y2 != 0:
                    y = c2 / (-1 * y2)
                    x = -(y1 * y + c1) / x1
                if x2 != 0 and y2 == 0:
                    x = c2 / (-1 * x2)
                    y = -(x1 * x + c1) / y1 
                if check(x,y):
                    intersect.append((int(x),int(y)))
                    
            # y축에 평행한 직선 
            if x1 == 0 and y1 != 0:
                y = -1 * c1 / y1
                if x2 != 0 and y2 != 0:
                    x = -(y2 * y + c2) / x2
                    if check(x,y):
                        intersect.append((int(x),int(y)))
                if x2 != 0 and y2 ==0:
                    x = -1 * c2 / x2
                    if check(x,y):
                        intersect.append((int(x),int(y)))
            # x축에 평행한 직선 
            if x1 != 0 and y1 == 0:
                x = -1 * c1 / x1
                if x2 != 0 and y2 != 0:
                    y = -(x2 * x + c2) / y2
                    if check(x,y):
                        intersect.append((int(x),int(y)))

                if x2 == 0 and y2 != 0:
                    y = -1 * c2 / y2
                    if check(x,y):
                        intersect.append((int(x),int(y)))
                        
    max_row,min_row,max_col,min_col = 0, 1001, 0, 1001
    for i in range(len(intersect)):
        max_row, min_row = max(max_row, intersect[i][0]), min(min_row, intersect[i][0])
        max_col, min_col = max(max_col, intersect[i][1]), min(min_col, intersect[i][1])
         
         
	# 이 부분이 잘 안풀렸다 
    answer = [['.'] * (max_row - min_row + 1) for _ in range(max_col - min_col + 1)]
    intersect.sort()
    std_x, std_y = intersect[0][0], intersect[0][1]
    for i in range(len(intersect)):
        x, y = intersect[i][0] - std_x, intersect[i][1] - std_y
        answer[y][x] = '*'
        
    ans = []
    for i in range(len(answer)):
        ans.append(''.join(answer[i]))
        
    return ans