교점에 별 만들기 - Kotlin

프로그래머스

문제 설명

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 함수를 완성해주세요.

 

 

나의 풀이

 이 문제는 알고리즘이 딱히 필요가 없는 구현 문제이다. 다음과 같이 구현하였다.

import kotlin.math.abs

class Solution {
    fun solution(line: Array<IntArray>): Array<String> {
        findStar(line)
        return makeStar()
    }

    val star = mutableSetOf<Pair<Int, Int>>()
    fun findStar(line: Array<IntArray>) {
        for (i in line.indices) {
            for (j in i + 1 until line.size) {
                val check : Long = line[i][0].toLong() * line[j][1].toLong() - line[j][0].toLong() * line[i][1].toLong()
                val first = line[i][1].toLong() * line[j][2].toLong() - line[i][2].toLong() * line[j][1].toLong()
                val second = line[i][2].toLong() * line[j][0].toLong() - line[i][0].toLong() * line[j][2].toLong()

                if (check == 0L) continue
                if (first % check != 0L || second % check != 0L) continue
                val x : Long = first / check
                val y : Long = second / check

                star.add(x.toInt() to y.toInt())
            }
        }
    }


    fun makeStar(): Array<String> {
        val n = star.maxOf { it.second }
        val s = star.minOf { it.second }
        val e = star.maxOf { it.first }
        val w = star.minOf { it.first }

        val answer = Array(n - s + 1) { CharArray(e - w + 1) }

        for ((y, i) in (w..e).withIndex()) {
            for ((x, j) in (n downTo  s).withIndex()) {
                if (star.contains(i to j))
                    answer[x][y] = '*'
                else
                    answer[x][y] = '.'
            }
        }
        return answer.map { it.joinToString("") }.toTypedArray()
    }
}