[Kotlin] Korean Coding Test - Programmers - Running Race

Question

Link

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 playersarray.

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)