[Kotlin] Korean Coding Test - Programmers - Running Race
Kotlin2023-09-13 19:01 (KST)
Question
A running race is held every year in Yan.The commentators call the name of the player who overtakes the player right in front of them.For example, when the first to third-place "mumu," "soe," and "poe" players were running in order, the commentators called "soe," and the second-place "soe" overtook the first-place "mumu."In other words, the player "soe" is changed to first place and the player "mumu" to second place.
When the parameters are the string arrangement players with the names of the competitors in order of the first to the current rank, and the string arrangement calls with the names sung by commentators, complete a solution function that returns them in order of first to last rank.
Restrictions
players
- 5 ≤ length of
players
≤ 50,000 - Players[i] means the name of the i-th player.
- The elements of
players
are made up of only lowercase letters. players
does not contain duplicate values.- 3 ≤ length of players[i] ≤ 10
callings
- 2 ≤ length of
callings
≤ 1,000,000 - The
callings
are made up of elements of players only. - The name of the first runner in the race is not called.
Input/Output Example
Input
- players: ["mumu", "soe", "poe", "kai", "mine"]
- callings: ["kai", "kai", "mine", "mine"]
Output: ["mumu", "kai", "mine", "soe", "poe"]
Solve
If the players
array length is n and the callings
array length is m, and the named competitor is located in the nth position by overtaking the previous competitor.
If you use Array or List, the time complexity is O(n) because you find a player called indexOf.In the worst case, for each element of the callings
array, the time complexity can be O(nm) by traversing the entire players
array.
On the other hand, Map has a time complexity of O(1) because it finds Value with Key.
To solve the problem, a variable that stores the current position of the players and a variable that stores the ranking of the players are made into a Map and used.In this case, the time complexity is O(n+m).
Code 1. Use arrays without considering time complexity
class Solution {
fun solution(players: Array<String>, callings: Array<String>): Array<String> {
for (i in callings.indices) {
val index = players.indexOf(callings[i]) // O(n)
val front = players[index - 1] // O(1)
players[index - 1] = players[index]
players[index] = front
}
return players
}
}
TEST 1 〉 Pass (31.24ms, 62.8MB)
TEST 2 〉 Pass (22.72ms, 63.3MB)
TEST 3 〉 Pass (18.91ms, 64.4MB)
TEST 4 〉 Pass (21.51ms, 64.6MB)
TEST 5 〉 Pass (31.95ms, 66.3MB)
TEST 6 〉 Pass (48.98ms, 81.6MB)
TEST 7 〉 Pass (632.18ms, 97.3MB)
TEST 8 〉 Pass (2599.56ms, 101MB)
TEST 9 〉 Failed (Timeout)
TEST 10 〉 Failed (Timeout)
TEST 11 〉 Failed (Timeout)
TEST 12 〉 Failed (Timeout)
TEST 13 〉 Failed (Timeout)
TEST 14 〉 Pass (22.42ms, 64.3MB)
TEST 15 〉 Pass (18.66ms, 63.6MB)
TEST 16 〉 Pass (23.34ms, 63.4MB)
Code 2. Use Map Considering Time Complexity
class Solution {
fun solution(players: Array<String>, callings: Array<String>): Array<String> {
val rank = players.mapIndexed { idx, name -> name to idx }.toMap().toMutableMap()
// No speed difference when changing to callings.forEach, callings.forEachIndexed
callings.forEach {
val index = rank.getOrDefault(it, 0)
// No speed difference when converting players to Map
val front = players[index - 1]
players[index - 1] = it
players[index] = front
rank[it] = index - 1
rank[front] = index
}
return players
}
}
TEST 1 〉 Pass (3.25ms, 61.6MB)
TEST 2 〉 Pass (2.78ms, 64MB)
TEST 3 〉 Pass (3.64ms, 60.9MB)
TEST 4 〉 Pass (3.63ms, 61.1MB)
TEST 5 〉 Pass (7.02ms, 72.8MB)
TEST 6 〉 Pass (13.57ms, 88.5MB)
TEST 7 〉 Pass (37.90ms, 97.2MB)
TEST 8 〉 Pass (50.42ms, 109MB)
TEST 9 〉 Pass (131.37ms, 124MB)
TEST 10 〉 Pass (242.71ms, 230MB)
TEST 11 〉 Pass (352.97ms, 365MB)
TEST 12 〉 Pass (323.21ms, 340MB)
TEST 13 〉 Pass (397.47ms, 359MB)
TEST 14 〉 Pass (2.90ms, 62.1MB)
TEST 15 〉 Pass (5.20ms, 61MB)
TEST 16 〉 Pass (4.10ms, 61.3MB)
Code 3. Change Map conversion method
HashMap is a little faster than MutableMap.
class Solution {
fun solution(players: Array<String>, callings: Array<String>): Array<String> {
val rank = hashMapOf<String, Int>()
val playersMap = hashMapOf<Int, String>()
for (i in players.indices) {
rank[players[i]] = i
playersMap[i] = players[i]
}
callings.forEach {
val index = rank.getOrDefault(it, 0)
val front = playersMap[index - 1]!!
playersMap[index - 1] = it
playersMap[index] = front
rank[it] = index - 1
rank[front] = index
}
val answer = Array(players.size) { "" }
playersMap.forEach { answer[it.key] = it.value }
return answer
}
}
TEST 1 〉 Pass (0.08ms, 62.4MB)
TEST 2 〉 Pass (0.09ms, 61.4MB)
TEST 3 〉 Pass (0.31ms, 61.3MB)
TEST 4 〉 Pass (1.43ms, 60.7MB)
TEST 5 〉 Pass (5.41ms, 69.9MB)
TEST 6 〉 Pass (15.38ms, 82.8MB)
TEST 7 〉 Pass (81.07ms, 98.4MB)
TEST 8 〉 Pass (88.18ms, 103MB)
TEST 9 〉 Pass (170.64ms, 122MB)
TEST 10 〉 Pass (380.62ms, 253MB)
TEST 11 〉 Pass (732.31ms, 368MB)
TEST 12 〉 Pass (344.46ms, 339MB)
TEST 13 〉 Pass (517.83ms, 361MB)
TEST 14 〉 Pass (0.10ms, 61.7MB)
TEST 15 〉 Pass (0.09ms, 62.4MB)
TEST 16 〉 Pass (0.09ms, 62.9MB)