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

문제 분해

1. 두 직선의 교점 구하기. 근데 x, y가 둘 다 정수인! => itertools의 combination으로 직선의 조합을 구하자.

2. 별을 찍어줄 수 있는 최대 범위 구하기. 그러기 위해선 x 좌표값 중 최대 최소, y 좌표값 중 최대 최소를 구해야됨. (상자를 그리기 위한 좌우, 상하를 구한다고 생각하면 된다.)

3. .(점) 으로 2차원 배열 초기화. x와 y의 최대 최소를 사용해서 초기화해야됨.

4. 교점에 속한 인덱스를 *(별)로 업데이트. 수학의 평행이동 개념을 사용한다. 배열에 접근하는 거니 좌표가 아닌 인덱스로 접근해야됨을 헷갈리지 말기.

5. row별로 join해서 return하기~

 

코드

주석으로 설명을 작성해 놓았다. 

from itertools import combinations

def solution(line):
    answer = []

    # 교점을 구하기 위한 두 선의 조합
    for two_lines in combinations(line, 2):
        line1 = two_lines[0]
        line2 = two_lines[1]

        A, B, E = line1[0], line1[1], line1[2]
        C, D, F = line2[0], line2[1], line2[2]

        # 교점의 좌표가 분모 0인지
        if A*D - B*C == 0:
            continue
        else: 
            x = (B*F - E*D)/(A*D - B*C)
            y = (E*C - A*F)/(A*D - B*C)
            # x,y 좌표가 모두 정수인지
            if float(x) == int(x) and float(y) == int(y):
                answer.append((int(x), int(y)))

    # x는 x끼리, y는 y끼리 구분
    all_x = []
    all_y = []
    for i in range(len(answer)):
        all_x.append(answer[i][0])
        all_y.append(answer[i][1])

    # x, y의 상하한
    top_x = max(all_x)
    bottom_x = min(all_x)
    top_y = max(all_y)
    bottom_y = min(all_y)

    # 2차원 배열 초기화
    # 추가 설명: +1 을 하는 이유는 양 끝 점도 포함되기 때문이다.
    res = [['.'] * (top_x - bottom_x + 1) for _ in range(top_y - bottom_y + 1)]

    # 교점은 *로 업데이트
    # 위에서부터 *로 업데이트하되, 평행이동 고려.
    
    # 추가 설명: 위에서부터 (y의 max에서부터, 2차원배열의 첫번째 인덱스가 [0]에서부터 와 동의) 별로 업데이트를 할 거기 때문에
    # y좌표를 기준으로 내림차순 정렬!
    answer.sort(key= lambda x: (x[1], x[0]), reverse=True) 
    
    # 추가 설명: y는 반복문에 따라 변해가고, top_y는 변하지 않음. 근데 인덱스는 증가하는 방향이어야하기 때문에 top_y - y 로 이 지점이 row 기준 0번째임을 평행이동으로 표현
    # 추가 설명: 기준으로 top_x를 잡았고 인덱스를 고려해 -1 진행
    for x, y in answer:
        res[top_y-y][x-top_x-1] = "*" # 인덱스 주의!

	# row별로 join
    result = [''.join(res[row]) for row in range(top_y - bottom_y + 1)]
    
    return result

평행이동에 대한 인덱싱이 이해하기 어려울 수도 있는데, 그냥 기준을 어디로 잡냐의 문제이다.

아래 사진을 확인하면 기준이 될 수 있는 부분이 기본적으로 이렇게 4가지가 있는데,

 필자는 용어 통일하는게 좋아서 언더라인 친 (top_x, top_y) 를 기준으로 인덱스를 옮겼던 것이다.