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

Kotlin |

Language : KO,EN

문제

링크

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)입니다.

RisingStarGraphStar.jpg

만약 정수로 표현되는 교점에 별을 그려 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다.

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

이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다. 따라서 정답은

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

입니다.

직선 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 크기 이내에서 표현됩니다.

별이 한 개 이상 그려지는 입력만 주어집니다.

입출력 예시

입출력 예 #1

  • 입력: [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]
  • 출력: ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]

입출력 예 #2

  • 입력: [[0, 1, -1], [1, 0, -1], [1, 0, 1]]
  • 출력: ["*.*"]

입출력 예 #3

  • 입력: [[1, -1, 0], [2, -1, 0]]
  • 출력: ["*"]

입출력 예 #4

  • 입력: [[1, -1, 0], [2, -1, 0], [4, -1, 0]]
  • 출력: ["*"]

참고 사항

두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

  • Ax + By + E = 0
  • Cx + Dy + F = 0
RisingStarExpression.png

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

풀이

참고 사항에 주어진 교점을 구하는 공식을 이용한다.

  • 공식에 따르면 line 원소들 간에 곱셈 계산을 해야한다.
  • line 원소가 최대 100,000이고 두 원소를 곱하면 최대 10^10으로 데이터 타입 Long을 사용해야 한다.

찾아낸 교점에서 최소 좌표와 최대 좌표를 구하여 격자판을 그린다.

  • 좌측 최상단 좌표(최소 X, 최대 Y)가 기준점(0, 0)이 된다.

코드

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

    /**
     * 두 직선의 교점 구하기
     */
    private fun findCrossPoint(line: Array<IntArray>): List<Pair<Int, Int>> {
        val point = mutableListOf<Pair<Int, Int>>()
        for (i in 0 until line.size - 1) {
            for (j in i + 1 until line.size) {
                val denominator = line[i][0].toLong() * line[j][1] - line[i][1].toLong() * line[j][0]
                // 분모가 0이면 평행 또는 일치하므로 건너뛰기
                if (denominator == 0L) continue

                val numeratorX = line[i][1].toLong() * line[j][2] - line[i][2].toLong() * line[j][1]
                val numeratorY = line[i][2].toLong() * line[j][0] - line[i][0].toLong() * line[j][2]
                // 교차점이 정수가 아니면 건너뛰기
                if (numeratorX % denominator != 0L || numeratorY % denominator != 0L) continue

                val x = (numeratorX / denominator).toInt()
                val y = (numeratorY / denominator).toInt()
                point.add(Pair(x, y))
            }
        }
        return point
    }

    /**
     * 격자판 그리기
     */
    private fun makeGrid(crossPoint: List<Pair<Int, Int>>): Array<String> {
        val minX = crossPoint.minOf { it.first }
        val minY = crossPoint.minOf { it.second }
        val maxX = crossPoint.maxOf { it.first }
        val maxY = crossPoint.maxOf { it.second }

        val grid = Array(maxY - minY + 1) { CharArray(maxX - minX + 1) { '.' } }
        for (i in crossPoint.indices) {
            grid[maxY - crossPoint[i].second][crossPoint[i].first - minX] = '*'
        }

        return Array(grid.size) { String(grid[it]) }
    }
}
테스트 1 〉	통과 (0.55ms, 59.9MB)
테스트 2 〉	통과 (7.91ms, 62MB)
테스트 3 〉	통과 (0.37ms, 60.9MB)
테스트 4 〉	통과 (17.78ms, 66MB)
테스트 5 〉	통과 (4.46ms, 61MB)
테스트 6 〉	통과 (2.01ms, 62.2MB)
테스트 7 〉	통과 (5.03ms, 63MB)
테스트 8 〉	통과 (0.32ms, 59.8MB)
테스트 9 〉	통과 (18.44ms, 61.8MB)
테스트 10 〉	통과 (18.71ms, 61.9MB)
테스트 11 〉	통과 (24.09ms, 61.2MB)
테스트 12 〉	통과 (34.77ms, 61.8MB)
테스트 13 〉	통과 (25.12ms, 62MB)
테스트 14 〉	통과 (22.76ms, 61.2MB)
테스트 15 〉	통과 (28.44ms, 59.7MB)
테스트 16 〉	통과 (19.27ms, 60.7MB)
테스트 17 〉	통과 (27.19ms, 61.7MB)
테스트 18 〉	통과 (25.87ms, 62.6MB)
테스트 19 〉	통과 (22.83ms, 60.2MB)
테스트 20 〉	통과 (16.42ms, 60.9MB)
테스트 21 〉	통과 (25.47ms, 63.5MB)
테스트 22 〉	통과 (0.35ms, 59.8MB)
테스트 23 〉	통과 (0.49ms, 60.9MB)
테스트 24 〉	통과 (0.28ms, 61.7MB)
테스트 25 〉	통과 (0.31ms, 61.7MB)
테스트 26 〉	통과 (0.29ms, 62.2MB)
테스트 27 〉	통과 (0.52ms, 61.4MB)
테스트 28 〉	통과 (0.47ms, 59.4MB)
테스트 29 〉	통과 (0.40ms, 59.4MB)

코드. 함수 findCrossPoint에서 map을 이용한 경우

class Solution {
    // ...
    private fun findCrossPoint(line: Array<IntArray>): List<Pair<Int, Int>> {
        val point = mutableListOf<Pair<Int, Int>>()
        for (i in 0 until line.size - 1) {
            for (j in i + 1 until line.size) {
                val (A, B, E) = line[i].map { it.toLong() }
                val (C, D, F) = line[j].map { it.toLong() }

                val denominator = A * D - B * C
                // 분모가 0이면 평행 또는 일치하므로 건너뛰기
                if (denominator == 0L) continue

                val numeratorX = B * F - E * D
                val numeratorY = E * C - A * F
                // 교차점이 정수가 아니면 건너뛰기
                if (numeratorX % denominator != 0L || numeratorY % denominator != 0L) continue

                val x = (numeratorX / denominator).toInt()
                val y = (numeratorY / denominator).toInt()
                point.add(Pair(x, y))
            }
        }
        return point
    }
    // ...
}
테스트 1 〉	통과 (0.91ms, 59MB)
테스트 2 〉	통과 (9.99ms, 63.5MB)
테스트 3 〉	통과 (0.59ms, 61MB)
테스트 4 〉	통과 (13.76ms, 66MB)
테스트 5 〉	통과 (5.20ms, 60.6MB)
테스트 6 〉	통과 (2.45ms, 60.6MB)
테스트 7 〉	통과 (8.01ms, 61.5MB)
테스트 8 〉	통과 (0.47ms, 61.5MB)
테스트 9 〉	통과 (97.31ms, 95.9MB)
테스트 10 〉	통과 (87.47ms, 93.8MB)
테스트 11 〉	통과 (82.76ms, 94.6MB)
테스트 12 〉	통과 (107.77ms, 94.8MB)
테스트 13 〉	통과 (154.47ms, 95.9MB)
테스트 14 〉	통과 (122.53ms, 95.6MB)
테스트 15 〉	통과 (92.45ms, 95.3MB)
테스트 16 〉	통과 (91.58ms, 95.9MB)
테스트 17 〉	통과 (117.70ms, 95.8MB)
테스트 18 〉	통과 (98.94ms, 93.5MB)
테스트 19 〉	통과 (101.00ms, 93.3MB)
테스트 20 〉	통과 (87.15ms, 94.5MB)
테스트 21 〉	통과 (126.05ms, 95.9MB)
테스트 22 〉	통과 (0.88ms, 59.6MB)
테스트 23 〉	통과 (0.54ms, 59.5MB)
테스트 24 〉	통과 (0.40ms, 62.6MB)
테스트 25 〉	통과 (0.89ms, 61.6MB)
테스트 26 〉	통과 (1.06ms, 60.9MB)
테스트 27 〉	통과 (0.57ms, 61.1MB)
테스트 28 〉	통과 (0.54ms, 59.3MB)
테스트 29 〉	통과 (0.34ms, 62.3MB)

민갤

Back-End Developer

백엔드 개발자입니다.