[Kotlin] Korean Coding Test - Programmers - Making a Star at the Junction
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 ..
Plain Text
1
2
3
4
5
6
7
8
9
10
11
"..........."
".....*....."
"..........."
"..........."
".*.......*."
"..........."
"..........."
"..........."
"..........."
".*.......*."
"..........." 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.
Plain Text
1
2
3
4
5
6
7
8
9
"....*...."
"........."
"........."
"*.......*"
"........."
"........."
"........."
"........."
"*.......*" 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.
line has a width (column) length of 3.
Each element of line is 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
Kotlin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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]) }
}
}Plain Text
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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
Kotlin
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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
}
// ...
}Plain Text
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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)
민갤
Back-End Developer
백엔드 개발자입니다.
[Kotlin] Korean Coding Test - Programmers - Check personality types
Programmer's Coding Test Problem Personality Type Examination
Kotlin
[Kotlin] Korean Coding Test - Programmers - Fibonacci Number
Programmer's coding test practice Fibonacci number kotlin
Kotlin