위클리 챌린지 #2. 별 만들기

(문제 설명)

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

 

입출력 예)line                                                  result

[[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인 경우 두 직선은 평행 또는 일치합니다.

 

---

( 문제 해설 )

 

우선 참고사항을 참고해서

 

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

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

 

해당 조건에 맞게 코드를 짜면 좌표계를 얻을 수 있습니다.

 

 

# 주어진 line 즉, 좌표들 중에서 2개씩 조합해서 참고사항대로 코드 짯을시 해당 사항에 맞는 좌표들을 출력

combiCoord = list(combinations(line, 2))
    coordinates = []
    coordinateX = []
    coordinateY = []
    
    for i in range(len(combiCoord)):
        # coordinate
        a, b, e = combiCoord[i][0]
        c, d, f = combiCoord[i][1]
        
        # 평행 or 일치
        if (a*d - b*c) != 0:
            x = (b*f - e*d) / (a*d - b*c)
            y = (e*c - a*f) / (a*d - b*c)
           
            if x.is_integer() and y.is_integer():
                coordinates.append([int(x), int(y)])
                coordinateX.append(int(x))
                coordinateY.append(int(y))

{(-4, 1), (0, 4), (4, -4), (-4, -4), (4, 1)}

이렇게 나온 좌표들을

4 4 -4 -4  # maxX, maxY, minX, minY

이렇게 변환해서 for문을 돌려야 합니다.
-4 1 ==> 3 0
0 4 ==> 0 4
4 -4 ==> 8 8
-4 -4 ==> 8 0
4 1 ==> 3 8

 

이걸 어떻게 변환할 수 있을지? 그것이 이문제의 핵심입니다. 그림으로 설명하겠습니다.

 

그림1_ 좌표이동 설명

그림2_ 좌표이동 설명

이렇게 적절하게 좌표이동이 완료되면

해당 좌표일 때 "*"을 출력하고 아니면 "."을 출력하게 하면 됩니다.

 

# maxX, maxY, minX, minY 이 값을 구하는 이유는 식을 이용하는데 필요하지만 더 필요한 부분은..

우리는 모든 것을 완성하고 그림을 그릴 때

 

"..........."  
".....*....."  
"..........."  
"..........."  
".*.......*."  
"..........."  
"..........."  
"..........."  
"..........."  
".*.......*."  
"..........."  

이렇게 별 바깥쪽에 "."이 있는 형태가 아니라

 

"....*...."  
"........."  
"........."  
"*.......*"  
"........."  
"........."  
"........."  
"........."  
"*.......*"  

이렇게 *을 기점으로 딱 떨어지게 그려야 합니다.

때문에 max값을 이용하여 높이와, 너비를 정확히 설정해서 출력하기 위해서도 사용합니다.

 

---

[ 코드 ]

from itertools import combinations


def solution(line):
    combiCoord = list(combinations(line, 2))
    coordinates = []
    coordinateX = []
    coordinateY = []
    
    for i in range(len(combiCoord)):
        # coordinate
        a, b, e = combiCoord[i][0]
        c, d, f = combiCoord[i][1]
        
        # 평행 or 일치
        if (a*d - b*c) != 0:
            x = (b*f - e*d) / (a*d - b*c)
            y = (e*c - a*f) / (a*d - b*c)
           
            if x.is_integer() and y.is_integer():
                coordinates.append([int(x), int(y)])
                coordinateX.append(int(x))
                coordinateY.append(int(y))
    
    # print(coordinates)
    
    # 2차원 set
    setCoordinates = set(list(map(tuple, coordinates)))
    
    maxX = max(coordinateX)
    minX = min(coordinateX)
    maxY = max(coordinateY)
    minY = min(coordinateY)
    
    height = maxY - minY + 1
    width = maxX - minX + 1
    # print(height, width)
    print(setCoordinates)
    
    changedCoordinates = []
    # 좌표 변환
    # 나온 테스트 케이스를 기반으로 교차검증을 통해 식을 만드는 수 밖에 안떠오름 실제로 그렇게함
    print(maxX, maxY, minX, minY)
    for x, y in setCoordinates:
        # print(x, y, "==>", maxY - y, x - minX)
        changedCoordinates.append([maxY - y, x - minX])
    
    answer = [["."] * width for _ in range(height)]
    # print(answer)
    for x, y in changedCoordinates:
        answer[x][y] = "*"
    # print(answer)
    ans = []
    for a in answer:
        tmp = ""
        for i in a:
            if i == ".":
                tmp += "."
            else:
                tmp += "*"
        ans.append(tmp)
    
    return ans

---

후기

 

검산 과정이 힘든..

약간 수학 문제 같은 문제