천소희

기록하는 개발자

업데이트:

카테고리:

/

태그: , , ,

문제

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

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

접근방법

  1. 심판이 이름을 부르면 추월이 발생
  2. 이름을 불린 선수와 앞등의 선수를 바꾼다
  3. callings 의 배열이 끝날 때까지 반복

해결

class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        var currentPlayers = players
        for (calling in callings) {
            currentPlayers = changeRank(currentPlayers, calling)
        }
        return currentPlayers
    }
    
    fun changeRank(players: Array<String>, name: String): Array<String> {
        val changePlayers = players
        val rank = players.indexOf(name)
        val firstPlayer = players[rank-1]
        
        changePlayers[rank-1] = name
        changePlayers[rank] = firstPlayer
        
        return changePlayers
    }
}

몇가지 문제의 타임아웃이 발생

List 구조로 진행하는 연산은 시간복잡도가 커짐

극단적으로 말해서 50000명의 선수 중 마지막에 찾아야 할 선수가 있다면 indexOf() 에 최대 50000(O(n))의 시간이 발생한다.

Dictionary 구조의 경우 해시 테이블로 구현되어 있기 때문에 O(1)이 시간복잡도가 걸린다.

해시 테이블은 Key, Value 로 데이터를 저장하는 자료구조 중 하나로 데이터를 빠르게 검색할 수 있음 → Key 값으로 데이터 조회를 하기 때문에 해시 함수를 한번만 실행하면 된다.

class Solution {
fun changeRank(players: MutableMap<Int, String>, name: String): MutableMap<Int, String>{
        val changePlayers: MutableMap<Int, String> = players
        val rank = players.filterValues{it == name}.keys

        for (ran in rank) {
            val first = players[ran] ?: ""
            val second = players[ran-1] ?: ""

            changePlayers[ran-1] = first
            changePlayers[ran] = second
        }
        return changePlayers
    }

    fun solution(players: Array<String>, callings: Array<String>): ArrayList<String> {
        var hashtable = mutableMapOf<Int, String>()
        var rank = 1
        players.map { player ->
            hashtable[rank] = player
            rank += 1
        }
        callings.map { calling ->
            hashtable = changeRank(hashtable, calling)
        }
        return ArrayList(hashtable.values)
    }
}

mutableMap으로 변환 시키는 과정을 추가하였더니 갯수가 적을 때는 확실히 빨라졌다가 결국 갯수가 많아지니 시간 초과가 뜬다. (2.xx ms → 0.9ms)

일일히 변환하는게 아닌 hashtable에 적용 players.forEachIndexed { index, s -> hastable[s] = index } 인덱스와 values로 등수와 이름을 hashtable에 넣을 수 있다.

class Solution {
    fun solution(players: Array<String>, callings: Array<String>): Array<String> {
        val hashtable = mutableMapOf<String, Int>()
        players.forEachIndexed { index, s -> hashtable[s] = index }

        callings.forEachIndexed { index, name ->
            // 해쉬 테이블에는 이름과 순위를 순서 상관 없이 저장
            val callRank = hashtable[name] ?: 0
            // 실제 데이터 변환은 players에서 이뤄짐
            val frontPlayer = players[callRank - 1]

            players[callRank - 1] = name
            players[callRank] = frontPlayer

            hashtable[name] = callRank - 1
            hashtable[frontPlayer] = callRank
        }
        return players
    }

}

참고