03/19 알고리즘 공부(72) - 달리기 경주

조건

얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.

선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.

제한조건

• 5 ≤ players의 길이 ≤ 50,000
  • players[i]는 i번째 선수의 이름을 의미합니다.
  • players의 원소들은 알파벳 소문자로만 이루어져 있습니다.
  • players에는 중복된 값이 들어가 있지 않습니다.
  • 3 ≤ players[i]의 길이 ≤ 10
• 2 ≤ callings의 길이 ≤ 1,000,000
  • callings는 players의 원소들로만 이루어져 있습니다.
  • 경주 진행중 1등인 선수의 이름은 불리지 않습니다.

입출력 예

players	callings	result
["mumu", "soe", "poe", "kai", "mine]"	["kai", "kai", "mine", "mine"]	["mumu", "kai", "mine", "soe", "poe"]

알고리즘 예상

1. 저번 햄버거 만들기때와 같은 실수를 하지 않기 위해서는 calling에 대해서 앞에서부터 반복하는 방법을 써야한다.
2. players 배열에 대해 접근할 수 있는 다른 배열을 만든 뒤 이름이 나오면 앞 인덱스와 자리를 바꾸는 방법을 사용할 것 같다.(변수 called 사용)

 

초기 코드

class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        var answer: Array<String> = arrayOf<String>()
        return answer
    }
}

 

내 코드

// 실패(시간초과)
class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        val answer = players.map { it }.toMutableList()
        
        for( i in callings ){
            val rank = answer.indexOf(i)
            answer[rank] = answer[rank-1]
            answer[rank-1] = i
        }
        
        return answer.toTypedArray()
    }
}

로직은 틀리지 않았으나 players가 최대 5만명이 있기 때문에 반복횟수가 굉장히 많아져서 발생한다. 특히 indexOf는 앞에서 부터 차례로 검사하기 때문에 시간초과가 걸린다. 따라서 indexOf를 대체할 수 있는 방법이 필요하다.

class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        val ranking = mutableMapOf<String, Int>()

        players.forEachIndexed { i, p ->
            ranking[p] = i
        }

        for (i in callings) {
            val rank = ranking[i] ?: 0
            val temp = players[rank - 1]
            ranking[i] = ranking[i]!! -1
            ranking[temp] = ranking[temp]!! + 1
            players[rank] = temp
            players[rank - 1] = i
        }
        return players
    }
}

MutableMap을 이용해서 풀었다. 인덱스를 좀 더 빠르게 가져오는 방법을 찾다가 발견한 메서드라 공부가 더 필요하다.

다른 사람의 풀이

class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        val playerIdxMap = hashMapOf<String, Int>()

        players.forEachIndexed { i, p ->
            playerIdxMap.put(p, i)
        }

        for (c in callings) {
            val idx = playerIdxMap[c]!!

            players[idx] = players[idx-1]
            players[idx-1] = c

            playerIdxMap.put(c, idx-1)
            playerIdxMap.put(players[idx], idx)
        }

        return players
    }
}

 

개선점 또는 배운점

1. 해시맵과 뮤터블 맵 등 맵 클래스에 대해서 좀 더 찾아볼 필요가 있다.