[Kotlin] Korean Coding Test - Programmers - Making a Star at the Junction
by 민갤
Back End /
Question
Given n straight lines that can be represented by Ax + By + C = 0, we want to draw a star in the integer coordinates of the intersection points of this straight line.
For example, if you draw five straight lines on a coordinate plane
- 2x - y + 4 = 0
- -2x - y + 4 = 0
- -y + 1 = 0
- 5x - 8y - 12 = 0
- 5x + 8y + 12 = 0
The coordinates of all nodes are (4, 1), (4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5), (-1.5, -0.19), and (-1.5, 1.0). Of these, the coordinates represented only by integers are (4, 1), (4, -4), (-4, -4), (-4, 1), and (0, 4).
If you draw a star at an intersection represented by an integer and represent it as a string, the part where the star is drawn is expressed as *, and the space where the grid lines intersect is expressed as ..
"..........."
".....*....."
"..........."
"..........."
".*.......*."
"..........."
"..........."
"..........."
"..........."
".*.......*."
"..........." At this point, the grid is infinitely wide, so you only need to indicate the minimum size to include all the stars. So here's the answer.
"....*...."
"........."
"........."
"*.......*"
"........."
"........."
"........."
"........."
"*.......*" An array line containing information about straight lines A, B, and C is given as a parameter. At this time, complete the solution function so that the minimum square containing all the stars is returned.
Restrictions
The longitudinal (row) length of a line is a natural number of not less than 2 and not more than 1,000.
linehas a width (column) length of 3.-
Each element of
lineis in the form [A, B, C]. - A, B, and C are integers greater than or equal to -100,000 and less than or equal to 100,000.
- No pair of straight lines with numerous nodes is given.
- If A = 0 and B = 0, it is not given.
The correct answer is expressed within 1,000 * 1,000 sizes.
Only one or more stars are drawn.
Input/Output example
Input/Output example #1
- Input: [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]
- Output: ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]
Input/Output example #2
- Input: [[0, 1, -1], [1, 0, -1], [1, 0, 1]]
- Output: ["*.*"]
Input/Output example #3
- Input: [[1, -1, 0], [2, -1, 0]]
- Output: ["*"]
Input/Output example #4
- Input: [[1, -1, 0], [2, -1, 0], [4, -1, 0]]
- Output: ["*"]
Notes
If there is only one intersection of two straight lines, the intersection is as follows.
- Ax + By + E = 0
- Cx + Dy + F = 0
In addition, if AD - BC = 0, the two straight lines are parallel or coincident.
Solve
Use the formula for finding the intersection given in the notes.
- According to the formula, multiplication calculations between line elements are required.
- If the line element is at most 100,000 and the two elements are multiplied, the data type Long should be used as at most 10^10.
Draw a grid by finding the minimum and maximum coordinates from the found intersection.
- The top left coordinates (minimum X, maximum Y) are the reference points (0, 0).
Code
class Solution {
fun solution(line: Array<IntArray>): Array<String> {
return makeGrid(findCrossPoint(line))
}
/**
* Find the intersection of two straight lines
*/
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]
// Skip because if the denominator is zero, it is parallel or coincident
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]
// Skip if the intersection is not an integer
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
}
/**
* Drawing a grid
*/
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]) }
}
}TEST 1 〉 Pass (0.55ms, 59.9MB)
TEST 2 〉 Pass (7.91ms, 62MB)
TEST 3 〉 Pass (0.37ms, 60.9MB)
TEST 4 〉 Pass (17.78ms, 66MB)
TEST 5 〉 Pass (4.46ms, 61MB)
TEST 6 〉 Pass (2.01ms, 62.2MB)
TEST 7 〉 Pass (5.03ms, 63MB)
TEST 8 〉 Pass (0.32ms, 59.8MB)
TEST 9 〉 Pass (18.44ms, 61.8MB)
TEST 10 〉 Pass (18.71ms, 61.9MB)
TEST 11 〉 Pass (24.09ms, 61.2MB)
TEST 12 〉 Pass (34.77ms, 61.8MB)
TEST 13 〉 Pass (25.12ms, 62MB)
TEST 14 〉 Pass (22.76ms, 61.2MB)
TEST 15 〉 Pass (28.44ms, 59.7MB)
TEST 16 〉 Pass (19.27ms, 60.7MB)
TEST 17 〉 Pass (27.19ms, 61.7MB)
TEST 18 〉 Pass (25.87ms, 62.6MB)
TEST 19 〉 Pass (22.83ms, 60.2MB)
TEST 20 〉 Pass (16.42ms, 60.9MB)
TEST 21 〉 Pass (25.47ms, 63.5MB)
TEST 22 〉 Pass (0.35ms, 59.8MB)
TEST 23 〉 Pass (0.49ms, 60.9MB)
TEST 24 〉 Pass (0.28ms, 61.7MB)
TEST 25 〉 Pass (0.31ms, 61.7MB)
TEST 26 〉 Pass (0.29ms, 62.2MB)
TEST 27 〉 Pass (0.52ms, 61.4MB)
TEST 28 〉 Pass (0.47ms, 59.4MB)
TEST 29 〉 Pass (0.40ms, 59.4MB)Code. Use of map in the function findCrossPoint
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
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
}
// ...
}TEST 1 〉 Pass (0.91ms, 59MB)
TEST 2 〉 Pass (9.99ms, 63.5MB)
TEST 3 〉 Pass (0.59ms, 61MB)
TEST 4 〉 Pass (13.76ms, 66MB)
TEST 5 〉 Pass (5.20ms, 60.6MB)
TEST 6 〉 Pass (2.45ms, 60.6MB)
TEST 7 〉 Pass (8.01ms, 61.5MB)
TEST 8 〉 Pass (0.47ms, 61.5MB)
TEST 9 〉 Pass (97.31ms, 95.9MB)
TEST 10 〉 Pass (87.47ms, 93.8MB)
TEST 11 〉 Pass (82.76ms, 94.6MB)
TEST 12 〉 Pass (107.77ms, 94.8MB)
TEST 13 〉 Pass (154.47ms, 95.9MB)
TEST 14 〉 Pass (122.53ms, 95.6MB)
TEST 15 〉 Pass (92.45ms, 95.3MB)
TEST 16 〉 Pass (91.58ms, 95.9MB)
TEST 17 〉 Pass (117.70ms, 95.8MB)
TEST 18 〉 Pass (98.94ms, 93.5MB)
TEST 19 〉 Pass (101.00ms, 93.3MB)
TEST 20 〉 Pass (87.15ms, 94.5MB)
TEST 21 〉 Pass (126.05ms, 95.9MB)
TEST 22 〉 Pass (0.88ms, 59.6MB)
TEST 23 〉 Pass (0.54ms, 59.5MB)
TEST 24 〉 Pass (0.40ms, 62.6MB)
TEST 25 〉 Pass (0.89ms, 61.6MB)
TEST 26 〉 Pass (1.06ms, 60.9MB)
TEST 27 〉 Pass (0.57ms, 61.1MB)
TEST 28 〉 Pass (0.54ms, 59.3MB)
TEST 29 〉 Pass (0.34ms, 62.3MB)
