(프로그래머스 JS KAKAO)가사 검색

https://programmers.co.kr/learn/courses/30/lessons/60060

코딩테스트 연습 - 가사 검색

Trie 알고리즘 활용.

 

물음표가 쿼리의 앞에 존재하는지, 뒤에 존재하는지에 따라 Trie 탐색을 다르게 해야 한다.

2가지의 Trie를 선언하여 단어를 저장하는데,

앞에서 단어를 검색하는 경우와 뒤에서 단어를 검색하는 경우를 저장하기 위함이다.

각 Trie를 frontTrie, backTrie라는 이름으로 선언했다.

 

우선 words에 있는 단어를 중복제거를 하여 newWords에 저장한다.

newWords 배열을 순회하면서 단어를 frontTrie와 backTrie에 저장한다.

backTrie에 저장하기 위해서는 단어를 뒤집어야 하기 때문에 split->reverse->join 하여 단어를 뒤집어서 저장한다.

 

Trie 클래스의 Node에는 특별히 childLength라는 객체를 추가적으로 만들었다.

이 객체는 저장하는 단어의 길이를 key로 가지며, value는 해당 길이의 단어 개수를 뜻한다.

 

예를들어, frodo, front, frozen이라는 단어를 Trie에 저장한다면,

f의 childLength = {

5: 2,

6, 1}

 

fr의 childLength = {

5: 2,

6, 1}

 

fro의 childLength = {

5: 2,

6: 1}

...

frodo의 childLength = {

5: 1}

 

front의 childLength = {

5: 1}

 

frozen의 childLength = {

6: 1}

 

이런식으로 저장하여 현재까지의 단어에서 가질 수 있는 단어의 길이와 개수를 쉽게 구할 수 있도록 하였다.

 

다음은 쿼리문을 돌면서 단어를 찾아야 한다.

현재 쿼리 단어의 접두사가 ?인지, 혹은 접미사가 ?인지 확인한다.

접미사가 ? 라면 frontTrie를 탐색하고,

접두사가 ? 라면 backTrie를 탐색한다.

backTrie를 탐색할 때에는 역시나 쿼리 단어를 split->reverse->join 하여 단어를 뒤집어서 탐색한다.

 

search 메소드를 에서 for문을 이용해서 string의 문자를 trie에서 찾는다.

만약 trie에서 문자를 찾을 수 없다면 바로 0을 리턴한다.

문자를 trie에서 찾을 때까지 탐색하는데 ?를 찾게 된다면 break.

현재 탐색하는 단어의 노드에서 childLength 객체를 활용하면 된다.

string의 length를 가지는 키값이 있다면 해당 length를 가지는 단어의 개수(value)를 리턴하여 카운팅.

없다면 0을 리턴하여 카운팅하면 된다.

 

class Node {
    constructor(value = ""){
        this.value = value;
        this.end = false;
        this.child = {};
        this.childLength = {};
    }
}

class Trie{
    constructor() {
        this.root = new Node();
    }
    
    insert(string){
        let currentNode = this.root;
        
        for(let i = 0; i < string.length; i++){
            const char = string[i];
            const length = currentNode.childLength[string.length];
            
            if(!currentNode.child[char]){
                currentNode.child[char] = new Node(currentNode.value + char);
            }
            
            currentNode.childLength[string.length] = length ? length + 1 : 1;
            currentNode = currentNode.child[char];
        }
        
        currentNode.end = true;
    }
    
    search(string){
        let currentNode = this.root;
        
        for(let i = 0; i < string.length; i++){
            const char = string[i];
            
            if(char === "?"){
                break;
            }
            
            if(currentNode.child[char]){
                currentNode = currentNode.child[char];
            } else{
                return 0;
            }
        }
        
        return currentNode.childLength[string.length] || 0;
    }
}

function solution(words, queries) {
    const answer = Array(queries.length).fill(0);
    const frontTrie = new Trie();
    const backTrie = new Trie();
    const check = new Map();
    
    const newWords = words.filter((word) => {
        if(check.has(word)){
            return false;
        }
        
        check.set(word, true);
        return true;
    });
    
    for(let i = 0; i < newWords.length; i++){
        const reverse = newWords[i].split("").reverse().join("");
        
        frontTrie.insert(newWords[i]);
        backTrie.insert(reverse);
    }
    
    for(let i = 0; i < queries.length; i++){
        const q = queries[i];
        
        if(q[0] !== "?"){
            answer[i] += frontTrie.search(q);
        } else{
            answer[i] += backTrie.search(q.split("").reverse().join(""));
        }
    }
    
    return answer;
}