프로그래머스 : 가사검색 JavsScript

자료구조 : 트라이

 

1년전 정리했던 자료구조이다. Java로 짜여져있는 내코드를 참조했다.

https://redbinalgorithm.tistory.com/167?category=880023 

트라이(Trie) : JAVA / 백준 5052

 

트라이 알고리즘은 특정 자료안에 key가 존재하는가 여부를 O(NM) 안에 알 수 있는 가장 빠른 자료구조이다(N은 쿼리수)

 

이러한 특성때문에 해당 프로그래머스 문제에서도 쿼리수가 많은 경우에도 빠르게 문제를 찾을 수 있다.

 

문제의 아이디어 words를 정방향, 역방향으로 문자의 길이 배열별로 트라이 자료구조를 생성한다. 

- 길이가 5인 word 정방향, 역방향

- 길이가 3인 word 정방향, 역방향

 

이렇게 생성해도 최대 40000개의 배열이 생성된다.

 

트라이 자료구조에 현재 index(여기서는 word의 몇번째 단어) 분기에서 단어가 몇개있는지 저장을 한다.

insert 마다 count++를 해주면 해당 분기에서 몇개의 단어가 등록되어있는지 알 수 있다.

 

따라서 트라이 구조를 만들고 queries를 탐색할 때 정방향 , 역방향 알맞게 find를 돌린다면, 처음으로 ?가 나오는 순간에 현재 노드의 등록된 단어수를 반환한다. 만약 null값이 나온다면 사전에 등록되어 있지 않다는 뜻이니 0을 반환한다.

 

const ALPHABET = 26;

class TrieNode {
    constructor(){
        this.children = Array(ALPHABET).fill(null);
        this.isEndOfWord = false;
        this.count = 0;
    }
}

function insert(key, root) {
    let level;
    let length = key.length;
    let index;

    root.count++;
    let pCrawl = root;
    
    for(level=0; level<length; ++level) {
        index = key[level].charCodeAt(0) - 'a'.charCodeAt(0);
        if(pCrawl.children[index] === null)
            pCrawl.children[index] = new TrieNode();
        pCrawl.children[index].count++;
        pCrawl = pCrawl.children[index];
    }
    pCrawl.isEndOfWord = true;
}

function find(key, root) {
    let level;
    let length = key.length;
    let index;
    let pCrawl = root;
    for(level=0;level<length;++level) {
        if(key[level] === '?')
            return pCrawl.count;
        index = key[level].charCodeAt(0) - 'a'.charCodeAt(0);
        if(pCrawl.children[index] === null)
            return 0;

        pCrawl = pCrawl.children[index];
    }

    return pCrawl.count;
}

const frontRoot = Array.from({length:10001},() => new TrieNode());
const rearRoot = Array.from({length:10001},() => new TrieNode());

function solution(words, queries) {
    
    // 정방향, 반대방향 Trie 길이별 생성
    for(let word of words) {
        let len = word.length;
        insert(word,frontRoot[len]);
        insert(word.split("").reverse().join(""),rearRoot[len]);
    }
    var answer = [];
    // 정답 찾기 query
    for(let query of queries) {
        // 정방향
        let len = query.length;
        if(query[0] !== '?') {
            answer.push(find(query,frontRoot[len]));
        }
        // 역방향
        else {
            answer.push(find(query.split("").reverse().join(""),rearRoot[len]))
        }
    }
    return answer;
}