[KOTLIN] 교점에 별 만들기

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

코딩테스트 연습 - 교점에 별 만들기

문제 설명

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

풀이

1. 주어진 조건에 맞게 x, y 좌표를 구한다.

2. 이때 각 점의 최대 값이 100,000 이므로 x, y 좌표를 구하는 수식(AD - BC 혹은 BF - ED 혹은 EC - AF)에서 Int 범위를 넘어가기 때문에 Long 타입으로 받는다.

3. 교점의 좌표를 중복을 허락하지 않고 저장하기 위해서 Set 자료구조에 저장 한다.

4. *을 찍을 좌표 크기를 구하기 위해서 3번의 Set 데이터를 이용하여 x, y 의 최대, 최소 값을 찾는다.

5. 교점의 좌표를 * 을 찍는 좌표계로 표현하기 위해 x, y 좌표를 변환하는 수식을 찾는다.

- x = maxY - y, y = x - minX

전체 코드

class Solution {
    // 각 점의 최대값이 100,000 이므로 좌표 계산후 나온 결과 값이 Int 범위를 넘어 갈 수 있다.
    // Long 으로 설정하여 값을 구한다.
    fun solution(line: Array<IntArray>): Array<String> {
        val coord = mutableSetOf<Pair<Long, Long>>()
        
        for (i in 0 until line.size) {
            val (A, B, E) = line[i].map { it.toLong() }
            for (j in (i + 1) until line.size) {
                val (C, D, F) = line[j].map { it.toLong() }
                val div = A * D - B * C
                val xDiv = B * F - E * D
                val yDiv = E * C - A * F

                // 두 직선이 평행선이라 교점이 없는 경우.
                if (div == 0L) continue
                
                // x, y 좌표가 정수가 아닌 경우.
                if (xDiv % div != 0L || yDiv % div != 0L) continue
                
                val x = xDiv / div
                val y = yDiv / div
                
                // 좌표를 중복을 허용하지 않고 저장
                coord.add(Pair(x, y))
                //println("result : $result")
            }
        }
        
        
        var maxX = Int.MIN_VALUE
        var minX = Int.MAX_VALUE
        var maxY = Int.MIN_VALUE
        var minY = Int.MAX_VALUE
        
        coord.forEach { co ->
            val x = co.first
            val y = co.second
            
            // 별표를 찍기 위한 정답 크기를 얻기 위해 x, y 최대 최소 값을 구함.
            minX = Math.min(minX, x.toInt())
            maxX = Math.max(maxX, x.toInt())
            minY = Math.min(minY, y.toInt())
            maxY = Math.max(maxY, y.toInt())
        }
        
        //println("$maxX, $minX, $maxY, $minY")
        // 좌표에 점찍기
        val width = maxX - minX + 1
        val height = maxY - minY + 1
        val matrix = Array(height) {
            CharArray(width) { '.' }
        }
        
        coord.forEach { co ->
            // 구해진 좌표의 x, y 를 바꾼후 좌표에 별을 찍을 위치를 구한다.
            // newX = maxX - x, newY = maxY + y
            val x = (maxY - co.second).toInt()
            val y = (co.first - minX).toInt()
            //println("x:$x, y:$y") 
            matrix[x][y] = '*'
        }
        
        val answer = Array(height) { "" }
        
        matrix.forEachIndexed { index, m ->
           answer[index] = String(m)
        }
        
        return answer
    }
}