[알고리즘 문제/2020 KAKAO BLIND RECRUITMENT] 가사 검색

해결 코드

insert할 때 입력된 현재 노드에서 도착할 수 있는 단어를 남은 글자수 별로 저장 (countEndOfWordPerDepth)
예를 들면, "frodo" 단어를 추가하면

root에 countEndOfWordPerDepth[5]++

root.children['f'].countEndOfWordPerDepth[4]++

root.children['f'].children['r'].countEndOfWordPerDepth[3]++

과 같이 저장해서 '?'가 나오기 전까지의 노드를 찾고 해당 노드에서 '?'의 갯수 즉 depth에 저장된 단어 수를 return하면 빠르게 정답을 도출할 수 있다.
2차 해결코드에서 하위노드를 돌며 정답을 계산하는 단계를 줄일 수 있음

import kotlin.test.*
import kotlin.time.*

data class TrieNode(val children : MutableMap<Char,TrieNode>, val countEndOfWordPerDepth : MutableMap<Int, Int>) 
class Trie {
    val root = TrieNode(mutableMapOf(), mutableMapOf())

    fun insert(word : String) {
        var currentNode = root
        var depthEndOfWord = word.length
        for(char in word) {
            val countEndOfWord = currentNode.countEndOfWordPerDepth[depthEndOfWord] ?: 0
            currentNode.countEndOfWordPerDepth[depthEndOfWord] = countEndOfWord + 1
            val child = currentNode.children[char] ?: TrieNode(mutableMapOf(), mutableMapOf())
            currentNode.children[char] = child
            currentNode = child
            depthEndOfWord--
        }
    }

    fun searchNodeWithQuery(query : String) : Pair<TrieNode, Int> {
        var currentNode = root
        var depthEndOfWord = query.length
        for(char in query) {
            if(char == '?') break
            val child = currentNode.children[char] ?: run{ return Pair(TrieNode(mutableMapOf(), mutableMapOf()), -1) }
            currentNode = child
            depthEndOfWord --
        }
        return Pair(currentNode, depthEndOfWord)
    }
}

class Solution {

    fun solution(words: Array<String>, queries: Array<String>): IntArray {
        var answer = mutableListOf<Int>()

        val normalTrie = Trie()
        val reverseTrie = Trie()

        for(word in words) {
            normalTrie.insert(word)
            reverseTrie.insert(word.reversed())
        }

        for(query in queries) {
            val isWildFirst = query.first().equals('?')
            val isWildLast = query.last().equals('?')
            val (node, depthEndOfWord) = when {
                isWildLast-> normalTrie.searchNodeWithQuery(query)
                else -> reverseTrie.searchNodeWithQuery(query.reversed())
            }
            answer.add(node.countEndOfWordPerDepth[depthEndOfWord] ?: 0 )
        }

        return answer.toIntArray()
    }
}

class SolutionTest(val solution : Solution, val testTool : TestStrategy = NormalTest()) {

    fun testTrieWordInsert() {
        val normalTrie = Trie()

        testTool.test(true) {
            normalTrie.insert("frodo")
            normalTrie.root.children['f'] != null
        }
    }

    fun testTrieWordInsertWithEndOfWordDepth() {
        val normalTrie = Trie()

        testTool.test(true) {
            normalTrie.insert("frodo")
            normalTrie.insert("front")
            val fCheck = normalTrie.root.children['f']!!.countEndOfWordPerDepth[4] == 2
            val oCheck = normalTrie.root.children['f']!!.children['r']!!.children['o']!!.countEndOfWordPerDepth[2] == 2
            val dCheck = normalTrie.root.children['f']!!.children['r']!!.children['o']!!.children['d']!!.countEndOfWordPerDepth[1] == 1
            fCheck && oCheck && dCheck
        }
    }

    fun testTrieReversedWordInsert() {
        val reverseTrie = Trie()

        testTool.test(true) {
            reverseTrie.insert("frodo".reversed())
            val fCheck = reverseTrie.root.children['f'] == null
            val oCheck = reverseTrie.root.children['o'] != null

            fCheck && oCheck
        }
    }

    fun testTrieReversedWordInsertWithEndOfWordDepth() {
        val reverseTrie = Trie()

        testTool.test(true) {
            reverseTrie.insert("frodo".reversed())
            reverseTrie.insert("front".reversed())
            val oCheck = reverseTrie.root.children['o']!!.countEndOfWordPerDepth[4] == 1
            val tCheck = reverseTrie.root.children['t']!!.countEndOfWordPerDepth[4] == 1
            val fCheck = reverseTrie.root.children['f'] == null
            oCheck && tCheck && fCheck
        }
    }

    fun testTrieWordSearch() {
        val words = arrayOf("frodo", "front", "frost", "frozen", "frame", "kakao")
        val normalTrie = Trie()

        for(word in words) {
            normalTrie.insert(word)
        }

        testTool.test(3) {
            val (node, answer) = normalTrie.searchNodeWithQuery("fro??")
            node.countEndOfWordPerDepth[answer] ?: 0 
        }
    }
    
    fun testTrieWordSearchNoChar() {
        val words = arrayOf("frodo", "front", "frost", "frozen", "frame", "kakao")
        val normalTrie = Trie()

        for(word in words) {
            normalTrie.insert(word)
        }

        testTool.test(1) {
            val (node, answer) = normalTrie.searchNodeWithQuery("??????")
            node.countEndOfWordPerDepth[answer] ?: 0 
        }
    }

    fun testSolution() {
        val words = arrayOf("frodo", "front", "frost", "frozen", "frame", "kakao")
        val queries = arrayOf("fro??", "????o", "fr???", "fro???", "pro?", "??????")
        val answer = intArrayOf(3, 2, 4, 1, 0, 1)

        testTool.test(answer.toList()) {
            solution.solution(words, queries).toList()
        }
    }

}

interface TestStrategy {
    fun<T> test(answer : T, testBlock: () -> T)
}

class NormalTest : TestStrategy {
    override fun<T> test(answer : T, testBlock: ()->T) {
        val result = testBlock()
        println("------------")
        assertEquals(answer, result, "epected : $answer, actural : $result")
    }
}

class EfficiencyTest : TestStrategy {
    override fun<T> test(answer : T, testBlock: ()->T) {
        val (result, duration) = measureTimedValue { testBlock() }
        println("------------")
        println("duration : $duration")
        assertEquals(answer, result, "epected : $answer, actural : $result")
    }
}

fun main() {
    val solution = Solution()
    val solutionTest = SolutionTest(solution, EfficiencyTest())

    solutionTest.testTrieWordInsert()
    solutionTest.testTrieWordInsertWithEndOfWordDepth()
    solutionTest.testTrieReversedWordInsert()
    solutionTest.testTrieReversedWordInsertWithEndOfWordDepth()
    solutionTest.testTrieWordSearch()
    solutionTest.testTrieWordSearchNoChar()
    solutionTest.testSolution()
}

 

2차 코드

Trie 적용, 여전히 효율성 테스트 1, 3 시간초과로 실패

import kotlin.test.*
import kotlin.time.*

data class TrieNode(var isEndOfWord : Boolean, val children : MutableMap<Char,TrieNode>)
class Trie {
    val root = TrieNode(false, mutableMapOf())

    fun insert(word : String) {
        var currentNode = root
        word.forEach{ char -> 
            val child = currentNode.children[char] ?: TrieNode(false, mutableMapOf())
            currentNode.children[char] = child
            currentNode = child
        }
        currentNode.isEndOfWord = true
    }

    fun search(word : String) : Boolean {
        var currentNode = root
        word.forEach{ char -> 
            val child = currentNode.children[char] ?: return false
            currentNode = child
        }
        return currentNode.isEndOfWord
    }

    fun searchNodeWithWild(wildString : String) : TrieNode? {
        var currentNode = root
        wildString.forEach{ char -> 
            if(char == '?') return currentNode
            val child = currentNode.children[char] ?: return null
            currentNode = child
        }
        return currentNode
    }

    fun countMatchChildWithWildCount(wildCount : Int, trieNode : TrieNode?) : Int {
        return trieNode?.run{ countMatchChildWithWildCount(wildCount, this, 0) }?: 0
    }

    private fun countMatchChildWithWildCount(wildCount : Int, trieNode : TrieNode, sum : Int) : Int {
        return if(wildCount <= 0) {
            if(trieNode.isEndOfWord) sum + 1 else sum
        } else {
            var value = sum
            trieNode.children.values.forEach {
                value += countMatchChildWithWildCount(wildCount-1, it, sum)
            } 
            value
        }
    }
}

class Solution {

    fun solution(words: Array<String>, queries: Array<String>): IntArray {
        var answer = mutableListOf<Int>()

        val normalTrie = Trie()
        val reverseTrie = Trie()

        for(word in words) {
            normalTrie.insert(word)
            reverseTrie.insert(word.reversed())
        }

        for(query in queries) {
            val isWildFirst = query.first().equals('?')
            val isWildLast = query.last().equals('?')
            val wildCount = query.count{ it.equals('?') }
            val count = when {
                isWildFirst && isWildLast-> normalTrie.countMatchChildWithWildCount(wildCount, normalTrie.root)
                isWildLast-> {
                    val trieNode = normalTrie.searchNodeWithWild(query)
                    normalTrie.countMatchChildWithWildCount(wildCount, trieNode)
                }
                isWildFirst-> {
                    val trieNode = reverseTrie.searchNodeWithWild(query.reversed())
                    reverseTrie.countMatchChildWithWildCount(wildCount, trieNode)
                }
                else -> 0
            }
            answer.add(count)
        }

        return answer.toIntArray()
    }
}

class SolutionTest(val solution : Solution, val testTool : TestStrategy = NormalTest()) {

    fun testTrieWordInsert() {
        val words = arrayOf("frodo", "front", "frost", "frozen", "frame", "kakao")
        testTool.test(true) {
            val normalTrie = Trie()
            for(word in words) {
                normalTrie.insert(word)
            }
            normalTrie.search("frost")
        }
    }

    fun testTrieReversedWordInsert() {
        val words = arrayOf("frodo", "front", "frost", "frozen", "frame", "kakao")
        testTool.test(true) {
            val reverseTrie = Trie()
            for(word in words) {
                reverseTrie.insert(word.reversed())
            }
            reverseTrie.search("nezorf")
        }
    }

    fun testSolution() {
        val words = arrayOf("frodo", "front", "frost", "frozen", "frame", "kakao")
        val queries = arrayOf("fro??", "????o", "fr???", "fro???", "pro?", "??????")
        val answer = intArrayOf(3, 2, 4, 1, 0, 1)

        testTool.test(answer.toList()) {
            solution.solution(words, queries).toList()
        }
    }

}

interface TestStrategy {
    fun<T> test(answer : T, testBlock: () -> T)
}

class NormalTest : TestStrategy {
    override fun<T> test(answer : T, testBlock: ()->T) {
        val result = testBlock()
        println("------------")
        assertEquals(answer, result, "epected : $answer, actural : $result")
    }
}

class EfficiencyTest : TestStrategy {
    override fun<T> test(answer : T, testBlock: ()->T) {
        val (result, duration) = measureTimedValue { testBlock() }
        println("------------")
        println("duration : $duration")
        assertEquals(answer, result, "epected : $answer, actural : $result")
    }
}

fun main() {
    val solution = Solution()

    val solutionTest = SolutionTest(solution, EfficiencyTest())

    solutionTest.testTrieWordInsert()
    solutionTest.testTrieReversedWordInsert()
    solutionTest.testSolution()
}

 

1차 코드

Trie 지식없이 선형적으로 문제 접근

import kotlin.test.*
import kotlin.time.*

class Solution {
    fun solution(words: Array<String>, queries: Array<String>): IntArray {
        var answer = mutableListOf<Int>()

        for(query in queries) {
            answer.add(searchQueryResultCount(words, query))
        }

        return answer.toIntArray()
    }

    fun searchQueryResultCount(words: Array<String>, query : String) : Int {

        val isWildFirst = query.first().equals('?')
        val isWildLast = query.last().equals('?')
        val wildCount = query.count({char -> char.equals('?')})

        val filteredWords = words.filter({word -> filterWordsWithQuery(word, query, isWildFirst, isWildLast, wildCount)})
        return filteredWords.size
    }

    fun filterWordsWithQuery(word: String, query: String, isWildFirst : Boolean, isWildLast : Boolean, wildCount : Int) : Boolean {
        return when {
            word.length != query.length -> false
            isWildFirst && isWildLast -> true
            isWildFirst -> word.subSequence(wildCount, word.length) == query.subSequence(wildCount, query.length)
            isWildLast -> word.subSequence(0, word.length - wildCount) == query.subSequence(0, query.length - wildCount)
            else -> false
        }
    }
}

class SolutionTest(val solution : Solution, val testTool : TestStrategy = NormalTest()) {

    fun testSolution() {
        val words = arrayOf("frodo", "front", "frost", "frozen", "frame", "kakao")
        val queries = arrayOf("fro??", "????o", "fr???", "fro???", "pro?")
        val answer = intArrayOf(3, 2, 4, 1, 0)

        testTool.test(answer.toList()) {
            solution.solution(words, queries).toList()
        }
    }

    fun testSearchQueryResultCount() {

        val words = arrayOf("frodo", "front", "frost", "frozen", "frame", "kakao")

        val testCase1 = Pair("fro??", 3)
        val testCase2 = Pair("????o", 2)
        val testCase3 = Pair("fr???", 4)
        val testCase4 = Pair("fro???", 1)
        val testCase5 = Pair("pro?", 0)
        val testCase6 = Pair("?????", 5)
        val testCase7 = Pair("?", 0)

        val testCases = listOf(testCase1 , testCase2, testCase3, testCase4, testCase5, testCase6, testCase7)

        testCases.forEachIndexed{ i, test ->
            val (query, answer) = test

            testTool.test(answer){
                solution.searchQueryResultCount(words, query)
            }
        }
    }
}

interface TestStrategy {
    fun<T> test(answer : T, testBlock: () -> T)
}

class NormalTest : TestStrategy {
    override fun<T> test(answer : T, testBlock: ()->T) {
        val result = testBlock()
        println("---------------------")
        assertEquals(answer, result, "epected : $answer, actural : $result")
    }
}

class EfficiencyTest : TestStrategy {
    override fun<T> test(answer : T, testBlock: ()->T) {
        val (result, duration) = measureTimedValue { testBlock() }
        println("---------------------")
        println("duration : $duration")
        assertEquals(answer, result, "epected : $answer, actural : $result")
    }
}

fun main() {
    val solution = Solution()
    val solutionTest = SolutionTest(solution, EfficiencyTest())

    solutionTest.testSolution()
}

 

이슈

효율성 테스트 1,2,3번 시간 초과로 해결하지 못함