Programmers Lv4) [2020 카카오블라인드] 가사검색

출처: programmers.co.kr/learn/courses/30/lessons/60060

분류: Kakao Blind 2020, Lv4, Trie

---

접근방식

효율성 문제였습니다. 대부분 정확성까지는 어렵지 않게 푸셨을 것 같은데요, 효율성에서 상당히 애를 먹었습니다 ㅠㅠ

문자열을 얼마나 효율적으로 관리하고 탐색할 수 있을지가 키포인트였던 것 같습니다 :) 카카오 단골이죠 문자열 ... 😇

 

문제설명

가사검색은 주어진 words가 있을 때 query에 만족하는 단어가 몇 개인지 찾는 문제였습니다.
쿼리는 ?를 포함하고 있는데요, ?는 한 글자를 의미하며 어떤 글자가 와도 괜찮습니다.

예를 들어 다음과 같다면, 

words = ["frodo", "front", "frost", "frozen", "frame", "kakao"] 
query = "fro??" 

쿼리를 만족하는 word는 frodo, front, frost 3개가 되겠죠? 
frozen은 글자 수가 달라서 매칭이 안 됩니다.

마지막으로 주의깊게 볼 포인트는
1. 쿼리에 ?는 무조건 포함되어야 하고, 중간이 아닌 앞 또는 뒤에만 올 수 있다는 점입니다. (덕분에 많은 케이스를 줄여준 것 같아요)  
2. words가 중복되지 않는다는 점입니다.

이 문제는 1차적으로 문자열을 앞에서부터 차례대로 탐색하면서 찾을 수도 있습니다.
길이가 같은 워드와 쿼리를 두고 ?가 앞이냐 뒤냐에 따라, ?가 아닌 부분부터 차례대로 돌면서 무사히 ?를 만나면 매칭이 되겠죠!

하지만 이렇게 하면 효율성을 통과하지 못합니다 ㅠㅠ
새로운 자료구조 Trie가 필요합니다!

문자열 관리

문자열을 빠르게 탐색하기 위해 새로운 자료구조 Trie를 학습했습니다. Trie의 자세한 내용은 따로 포스팅 하겠습니다 :)

Trie는 한 글자를 노드로 갖는 트리형태의 자료구조입니다.
단어의 길이가 최대 10,000 이므로 문자의 길이 별로 10,000개의 Trie를 만들어 줍니다. 
그리고 ?가 앞에서 시작할 수 있을 수 있으므로 역순으로 저장하는 Trie도 만들어 줍니다.

하지만 이렇게 까지만 하면 역시 효율성을 통과하지 못합니다.
핵심은 Trie의 개수를 카운트 해주는 것입니다.
조건에서 words는 중복이 없다고 명시해주고 있으니
Trie에 단어를 추가해줄 때 개수를 카운트해줍니다.

이렇게 하면 쿼리로 트라이를 탐색하다가 ?를 만났을 때 밑의 개수를 바로 알아낼 수 있습니다 🤭

 

해결방법

문제 해결에 필요한 부분만 간단하게 구현했습니다.

TrieNode 트라이 노드를 Generic으로 만들어 봤습니다. Trie는 딕셔너리로 관리하기 때문에 당연히 Hashable 이어야겠죠?

class TrieNode<T: Hashable> {
    var value: T?
    var count = 0
    weak var parentNode: TrieNode?
    var children = [T:TrieNode]()
    
    init(value: T? = nil, parentNode: TrieNode? = nil) {
        self.value = value
        self.parentNode = parentNode
    }
    
    func add(value: T) {
        guard children[value] == nil else { return }
        children[value] = TrieNode(value: value, parentNode: self)
    }
}

 

Trie는 insert 해주는 부분과, query를 탐색해서 개수를 리턴해주는 함수만 만들어봤습니다.
childCount는 그냥 트리를 타고 내려가다가 "?"를 만나면 개수를 리턴해줍니다 :)

class Trie {
    typealias Node = TrieNode<Character>
    fileprivate let root: Node
    
    init() {
        root = Node()
    }
}

extension Trie {
    
    func childCount(query: String) -> Int {
        guard !query.isEmpty else { return 0 }
        
        var currentNode = root
        for char in query {
            if char == "?" {
                return currentNode.count
            }
            guard let childNode = currentNode.children[char] else {
                return 0
            }
            currentNode = childNode
        }
        return currentNode.children.count
    }
    
    func insert(word: String) {
        guard !word.isEmpty else { return }
        
        var currentNode = root
        for char in word {
            currentNode.count += 1
            if let childNode = currentNode.children[char] {
                currentNode = childNode
            } else {
                currentNode.add(value: char)
                currentNode = currentNode.children[char]!
            }
        }
    }
}

 

앞서 말씀드린 대로 단어 길이가 10,000개 밖에 안 되므로 미리 Trie를 만들어서 해도 좋은데요,
저는 처음에 word의 길이가 아니라 words의 길이로 생각해서... 100,000개씩 만들어야 된다고 생각을 했어요 ㅠㅠ
그래서 미리 만들어두지 않고 단어의 길이를 key로 해서 그냥 딕셔너리로 구현했습니다. 그래서 코드가 조금 지저분하네요..!
메인 코드입니다.

func solution(_ words:[String], _ queries:[String]) -> [Int] {
    var tries = [Int:Trie]()
    var reverseTries = [Int:Trie]()
    var result = [Int]()
    
    for word in words {
        if let trie = tries[word.count] {
            trie.insert(word: word)
        } else {
            tries[word.count] = Trie()
            tries[word.count]?.insert(word: word)
        }
        
        if let trie = reverseTries[word.count] {
            trie.insert(word: String(word.reversed()))
        } else {
            reverseTries[word.count] = Trie()
            reverseTries[word.count]?.insert(word: String(word.reversed()))
        }
    }
    
    for query in queries {
        let prefix = query.first == "?"
        if prefix {
            if let trie = reverseTries[query.count] {
                result.append(trie.childCount(query: String(query.reversed())))
            } else {
                result.append(0)
            }
        } else {
            if let trie = tries[query.count] {
                result.append(trie.childCount(query: query))
            } else {
               result.append(0)
           }
        }
    }
    return result
}

 

배운점

정확성까지는 오 할만한데? 하고 풀었으나... 효율성에 상당한 애를 먹었습니다.
Trie라는 개념이 없다면 효율성 부분에 접근 자체가 어려웠던 문제같습니다 (저처럼요..) ㅠㅠ
덕분에 새로운 자료구조를 하나 배웠네요 ㅎㅎ
물론 Trie 말고도 다른 방법도 있겠죠?? 혹 알고 계시다면 댓글로 알려주시면 감사하겠습니다!! 🙏

풀고나니 4단계 문제였네요 ㄷㄷ.. 
4단계 처음 풀어보는 것 같아요 👏

감사합니다!