[Kotlin] 프로그래머스 - 교점에 별 만들기
by 민갤
Back End /
문제
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 크기 이내에서 표현됩니다.
별이 한 개 이상 그려지는 입력만 주어집니다.
입출력 예시
입출력 예 #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
또, 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)
