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

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

프로그래머스

문제를 보자마자

'선들의 교점을 구하라고??

공식을 어떻게 적용하지??'

라는 생각이 떠오르실 겁니다.

다행히 문제 맨 아래 참고사항에

이런 참고자료가 있으니

이 공식을 그대로 쓰시면 됩니다.

 

제가 푼 순서는 이렇습니다.

 

1. 교점 여부 판단

-->AD-BC=0인 경우 이외의 케이스만을 구했습니다.

 

2. 교점이 정수인지 판단

-->

이 공식을 사용했을 때

x와 y가 정수가 나오는 값만 구해야합니다.

분모에 해당하는 값으로 분자를 나눴을때

나머지가 0이라면 정수가 됩니다.

x같은 경우에는 (BF-ED)/(AD-BC)의 나머지가 0인 경우

y같은 경우에는 (EC-AF)/(AD-BC)의 나머지가 0인 경우

이 두가지를 모두 만족해야합니다.

참고로 좌표를 저장할 때, 저는 중복을 막기 위해 set (집합)을 사용했습니다.

 

3. 이제 좌표평면 입력해주기

-->이 부분이 체감상 가장 까다로웠습니다.

어떻게 무한히 큰 좌표에서

일부분만 나타날지 고민이 많이 되었습니다.

3-1 좌표들의 최대최소값을 구하고 그 범위만큼 '.'를 찍음

3-2 교점에 해당하는 좌표에 '*' 입력

3-3 역순으로 다시 문자열로 받아준다

 

def solution(line):
    answer = []
    temp = set()
    # 1. 교점이 있는지 판단하기
    # 2. 교점 구하기

    for i in range(len(line)):
        for k in range(i + 1, len(line)):
            # 1 교점여부 판단
            if line[i][0] * line[k][1] - line[i][1] * line[k][0] != 0:

                # 2 교점이 있다면
                # 정수인지 아닌지 판단
                if (line[i][1] * line[k][2] - line[i][2] * line[k][1]) % (
                        line[i][0] * line[k][1] - line[i][1] * line[k][0]) == 0 and (
                        line[i][2] * line[k][0] - line[i][0] * line[k][2]) % (
                        line[i][0] * line[k][1] - line[i][1] * line[k][0]) == 0:
                    x = (line[i][1] * line[k][2] - line[i][2] * line[k][1]) // (
                                line[i][0] * line[k][1] - line[i][1] * line[k][0])
                    y = (line[i][2] * line[k][0] - line[i][0] * line[k][2]) // (
                                line[i][0] * line[k][1] - line[i][1] * line[k][0])

                    temp.add((x, y))
    temp = list(temp)

    # 3 좌표평면 출력
    # 3-1 범위구하기
    x_min = temp[0][0]
    x_max = temp[0][0]
    y_min = temp[0][1]
    y_max = temp[0][1]

    for a, b in temp:
        x_min = min(x_min, a)
        x_max = max(x_max, a)
        y_min = min(y_min, b)
        y_max = max(y_max, b)

    # 3-2 교점이 있는 곳만 점으로 찍기
    ja = []
    for y in range(y_max + 1 - y_min):
        tmp = []
        for x in range(x_max + 1 - x_min):
            tmp.append('.')
        ja.append(tmp)

    for a, b in temp:
        ja[b - y_min][a - x_min] = '*'

    # 3-3 다시 좌표별로 입력하기
    for i in range(len(ja)):
        tmp = ''
        for j in range(len(ja[i])):
            tmp += ja[i][j]

        answer.insert(0, tmp)
    return answer