[파이썬] 프로그래머스 - 위클리 챌린지 10주차

• 교점에 별 만들기

문제 설명

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

---

입출력 예

lineresult

[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]	["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]
[[0, 1, -1], [1, 0, -1], [1, 0, 1]]	["*.*"]
[[1, -1, 0], [2, -1, 0]]	["*"]
[[1, -1, 0], [2, -1, 0], [4, -1, 0]]	["*"]

---

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

직선 y = 1, x = 1, x = -1는 다음과 같습니다.

(-1, 1), (1, 1) 에서 교점이 발생합니다.

따라서 정답은

"*.*"

입니다.

입출력 예 #3

직선 y = x, y = 2x는 다음과 같습니다.

(0, 0) 에서 교점이 발생합니다.

따라서 정답은

"*"

입니다.

입출력 예 #4

직선 y = x, y = 2x, y = 4x는 다음과 같습니다.

(0, 0) 에서 교점이 발생합니다.

따라서 정답은

"*"

입니다.

---

참고 사항

Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.

 

---

def isParallel(line1, line2):
    if (line1[0] * line2[1] - line1[1] * line2[0]) == 0:
        return True
    else:
        return False


def returnXY(line1, line2):
    X = (line1[1] * line2[2] - line1[2] * line2[1]) / (line1[0] * line2[1] - line1[1] * line2[0])
    Y = (line1[2] * line2[0] - line1[0] * line2[2]) / (line1[0] * line2[1] - line1[1] * line2[0])
    return [X, Y]


def solution(line):
    tmp_answer = [["." for y in range(2001)] for x in range(2001)]
    up, down, left, right = 0, 2000, 2000, 0
    first = False
    X_, y_ = 0, 0
    
    for i in range(len(line)):
        for j in range(i + 1, len(line)):
            if isParallel(line[i], line[j]) == False:
                X, Y = returnXY(line[i], line[j])
                
                if X == int(X) and Y == int(Y):
                    if first == False:
                        first = True
                        X_, Y_ = int(X) , int(Y)
                    
                    X, Y = int(X) - X_, int(Y) - Y_
                    
                    tmp_answer[X][Y] = "*"

                    if Y > up:
                        up = Y
                    if Y < down:
                        down = Y
                    if X > right:
                        right = X
                    if X < left:
                        left = X

    answer = []
    for y in range(up, down-1, -1):
        tmp = ""
        for x in range(left, right + 1):
            if tmp_answer[x][y] == "*":
                tmp += "*"
            else:
                tmp += "."

        answer.append(tmp)

    return answer

 

정확성  테스트
테스트 1 〉	통과 (139.14ms, 41.8MB)
테스트 2 〉	통과 (158.36ms, 42.4MB)
테스트 3 〉	통과 (138.50ms, 41.8MB)
테스트 4 〉	통과 (191.74ms, 42.7MB)
테스트 5 〉	통과 (158.44ms, 42MB)
테스트 6 〉	통과 (133.14ms, 41.9MB)
테스트 7 〉	통과 (157.69ms, 42.3MB)
테스트 8 〉	통과 (141.06ms, 41.8MB)
테스트 9 〉	통과 (474.40ms, 42.1MB)
테스트 10 〉	통과 (522.34ms, 42MB)
테스트 11 〉	통과 (591.77ms, 42MB)
테스트 12 〉	통과 (654.12ms, 42MB)
테스트 13 〉	통과 (644.75ms, 42.1MB)
테스트 14 〉	통과 (651.83ms, 42.3MB)
테스트 15 〉	통과 (601.87ms, 41.9MB)
테스트 16 〉	통과 (513.04ms, 41.9MB)
테스트 17 〉	통과 (608.38ms, 42MB)
테스트 18 〉	통과 (652.16ms, 42.1MB)
테스트 19 〉	통과 (560.24ms, 42MB)
테스트 20 〉	통과 (547.43ms, 41.9MB)
테스트 21 〉	통과 (536.66ms, 42.2MB)
테스트 22 〉	통과 (141.55ms, 41.8MB)
테스트 23 〉	통과 (151.20ms, 41.9MB)
테스트 24 〉	통과 (170.87ms, 41.9MB)
테스트 25 〉	통과 (142.81ms, 41.9MB)
테스트 26 〉	통과 (145.45ms, 41.9MB)
테스트 27 〉	통과 (174.33ms, 41.9MB)
테스트 28 〉	통과 (147.93ms, 41.9MB)
테스트 29 〉	통과 (140.28ms, 41.8MB)

 

후기

 수학은 문제에서 공식을 제시해주어서 다행이였다. 구현하는게 까다로운 부분이 있었다.

 

풀이

 (1) 평행이 아닐 경우 접점을 구했다. 선과 선이 접하는 X, Y좌표는 문제에서 제시한 공식을 그대로 사용했다.(정수가 아닌 X,Y좌표는 꼭 버려야 했다)

 (2) 2차원 리스트를 만들고 그곳의 X, Y 좌표에 별을 찍는다. (하지만 X, Y 좌표가 최대 100,000*100,000 일 수도 있어서 맨처음에 그냥 2차원 리스트를 만들어버리면 높은 확률로 런타임 에러가 뜬다.)

 (3) 문제에서 출력하는 것은 1000*1000이라고 하였기 때문에, 간단하게 생각하면 맨처음 X, Y를 좌표를 구하고 해당 X, Y좌표로부터 상하좌우 1000씩 즉 2000*2000이라면 전부 담을 수 있을 것이라고 생각하였다.

 (4) 별을 찍는 도중에 맨위, 맨아래, 맨오른쪽, 맨왼쪽 구간을 구하고 이렇게 얻은 구간들을 사용하여 별을 출력하였다.