2020 카카오 공채 코딩테스트 - 가사검색

2020 카카오 공채 코딩테스트 - 가사검색

코틀린 풀이

 

 

 

최종 풀이는 맨 아래에 있습니다.

 

 

 

 

 

 

최초 풀이과정)

실제 정확도 부분의 정답률은 30%가 넘어가는데 반해 효율성 테스트에서 정답률이 1%가 안되는 문제.

queries에 담겨있는 단어를 words의 단어와 하나씩 비교하며 조건을 판단하면 절대 통과를 못할 것으로 예상하여 

나름대로 해시맵 구조를 이용해 대상 words의 갯수을 낮추어 보았는데 그래도 효율성에서 1/3밖에 득점하지 못했다.

트라이와 이진탐색을 조합하면 시간복잡도를 낮추는 게 가능한 걸로 보인다.

 

 

 

사용언어 : 코틀린 Kotlin 

 

최초 풀이)

 

fun solution(words: Array<String>, queries: Array<String>): IntArray {
    var answer = IntArray(queries.size) {0}
    val wordsHashMap = mutableMapOf<Int, MutableList<String>>()
 
    for (word in words) {
        var wordLength = word.length
 
        if (!wordsHashMap.containsKey(wordLength)) {
            wordsHashMap[wordLength] = mutableListOf(word)
        }
        else {
            wordsHashMap[wordLength]?.add(word)
        }
 
    }
 
    for ( (index, query) in queries.withIndex() ) {
        var queryLength = query.length
        var fitLengthWords = wordsHashMap[queryLength]
        var count = 0
 
        if (fitLengthWords != null) {
            for(fitLengthWord in fitLengthWords) {
                for(i in fitLengthWord.indices) {
                    if(query[i] != '?' && query[i] != fitLengthWord[i]) {
                        break
                    }
 
                    if(i == fitLengthWord.lastIndex) {
                        count++
                    }
 
                }
            }
        }
 
        answer[index] = count
    }
 
    return answer
}

 

 

 

 

최종 풀이)

Trie 구조를 이용하여 마무리를 해보았다. 

일단 앞선 풀이에서는 애초에 문제를 잘못 이해하고 풀어서 삽질을 하고 있었...

와일드카드 문자인 '?' 는 접두사나 접미사에만 붙을 수 있는데 나는 '?a?vbv??w' 와 같은 경우도 고려하고 있었다...

문제를 다시 차근차근 읽고 Trie 구조를 이용하니 생각보다 쉽게 풀렸다.

 

일단 해당 단어를 포함하는 Trie 와

역순으로 된 단어를 포함하는 Trie 를 따로 만들어주어야 한다.

그리고 포함하고 있는 단어의 길이에 따라 Trie 를 다시 분류해야 한다.

 

각 노드의 속성에 count를 추가해주는데 해당 속성은 하위 노드에서 포함하고 있는 모든 단어의 갯수를 의미한다.

원래는 재귀함수를 이용하여 풀었는데 효율성에서 통과가 안되는 바람에 다른 방식을 적용하였다.

add를 통해 단어를 하나씩 추가하면서 특정 노드를 지날 때마다 해당 노드의 count를 하나씩 올려주면 된다.

주의해야 할 점은 rootNode의 경우는 초기화 시 count를 0으로 해주어야 한다.

(하위 노드들은 단어가 추가될 때 생기는 반면, rootNode의 경우 기본적으로 생성되는 노드이기 때문)

 

추가로 query 비교 시 모든 문자가 와일드카드로 이루어진 경우도 고려해야 오답이 나오지 않는다.

ex) "?????"

 

 

최종 풀이)

class Solution {
    fun solution(words: Array<String>, queries: Array<String>): IntArray {
        val answer = IntArray(queries.size) {0}
        val tries = mutableMapOf<Int, Trie>()
        val reverseTries = mutableMapOf<Int, Trie>()
 
        // Trie 구조화
        for (word in words) {
            val wordLength = word.length
            tries[wordLength]?.add(word) ?: tries.put(wordLength, Trie().also { it.add(word) })
        }
 
        // 뒤집은 단어 Trie 구조화
        for (word in words) {
            val wordLength = word.length
            reverseTries[wordLength]?.add(word.reversed()) ?: reverseTries.put(wordLength, Trie().also { it.add(word.reversed()) })
        }
 
        // 모든 쿼리에 대한 작업 수행
        for ( (index, query) in queries.withIndex() ) {
            val queryWithNoWildCard = query.replace("?", "")
            val queryLength = query.length
 
            when {
                queryWithNoWildCard.isEmpty() -> {
                    answer[index] = tries[queryLength]?.rootNode?.count ?: 0
                }
                query.startsWith('?') -> {
                    answer[index] = reverseTries[queryLength]?.let { it.getNode(queryWithNoWildCard.reversed())?.count ?: 0 } ?: 0
                }
                else -> {
                    answer[index] = tries[queryLength]?.let { it.getNode(queryWithNoWildCard)?.count ?: 0 } ?: 0
                }
            }
 
        }
 
        return answer
    }
 
}
class TrieNode {
    val childNode: MutableMap<Char, TrieNode> = mutableMapOf()
    var count: Int = 1
}
 
class Trie {
    val rootNode = TrieNode()
    init {
        this.rootNode.count = 0
    }
 
    fun add(word: String) {
        var tempNode = this.rootNode
        rootNode.count++
 
        for(char in word) {
            val tempChildNode = tempNode.childNode[char]
            tempNode = tempChildNode?.apply { count++ } ?: tempNode.childNode.computeIfAbsent(char) { TrieNode() }
        }
    }
 
    fun getNode(word: String): TrieNode? {
        var tempNode = this.rootNode
 
        for((index, char) in word.withIndex()) {
            val node = tempNode.childNode[char] ?: return null
            tempNode = node
        }
 
        return tempNode
    }
}