가사 검색

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

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

선형형 풀이

효율성 테스트 2번은 선형형 풀이로는 더이상 안되는 것 같다.

Trie 풀이로 변경 예정

function solution(words, queries) {
    let lenArray = new Array();
    let results = new Array(queries.length).fill(0);
    let map = new Map();
    
    for(let word of words){
        let len = word.length;
        
        if(lenArray[len] == null){
            lenArray[len] = new Array();   
        }
        lenArray[len].push(word);
    }
    
    for(let idx = 0; idx < queries.length; idx++){
        let query = queries[idx];
        
        //효율성 테스트 1
        if(map.has(query)) {
            results[idx] = map.get(query);
            continue;
        }
        
        let len = query.length;
        let curArr = lenArray[query.length];
        let startIdx = 0;
        let endIdx = len - 1;
        
        if(curArr == null) continue;
        
        //효율성 테스트 3
        while(startIdx <= endIdx){
            let flag = false;
            if(query.charAt(startIdx) == '?') {
                flag = true;
                startIdx++;
            }
            if(query.charAt(endIdx) == '?') {
                flag = true;
                endIdx--;
            }
            if(!flag) break;
        }
        if(endIdx < startIdx){
            results[idx] = curArr.length;
            continue;
        }
        
        let keyword = query.slice(startIdx,endIdx+1);
        for(let i = 0; i < curArr.length && startIdx <= endIdx; i++){
            if(keyword == curArr[i].slice(startIdx,endIdx+1)) results[idx]++;
        }
        
        map.set(query,results[idx]);
    }
    
    return results;
    
}

 

Trie로 수정했다. 

하기에서 사용한 Trie 코드는 

https://velog.io/@teihong93/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-Trie-%EA%B5%AC%ED%98%84

이 사이트를 참고 했다.

Trie를 사용한 해결 방법은 타 사이트를 보면 될 거 같고 효율성 테스트에 대해서만 여기에 남기고자 한다.

- 효율성 테스트 1번 : 동일한 값에 대한 return 처리를 해주면 된다. 하기 코드에는 넣지 않고도 통과 했는데, 코드가 최적화 되면 괜찮은 것으로 보인다.

- 효율성 테스트 2번 : Trie 구조를 사용해야지만 풀수 있다. (상위 선형 참고)

- 효율성 테스트 3번 : '?' <- 이거 즉각 return 처리

class Node {
    constructor(value = ''){
        this.value = value;
        this.map = {};
        this.count = 0;
    }
}

상기 보면 count를 처리하는데, length 별로 Trie를 관리 한다는 전제 하에 자신 Node를 스쳐가면 count 를 1을 더하면 된다.

-효율성 테스트 4번/5번 : Trie 구조에 문제가 있거나, Reverse 처리를 해야한다.

    for(let i = 0; i < words.length; i++) {
        if(rLen[words[i].length] == null) rLen[words[i].length] = new Trie();
        rLen[words[i].length].insert(words[i].split('').reverse().join(''));
    }

 

최종 코드

class Node {
    constructor(value = ''){
        this.value = value;
        this.end = false;
        this.child = {};
        this.count = 0;
    }
}

class Trie {
    constructor(){
        this.root = new Node();
    }

    insert(string){
        let currentNode = this.root;
        currentNode.count++;

        for(let i = 0; i <string.length ; i++) {

            const currentChar = string[i];

            if(currentNode.child[currentChar] === undefined){
                currentNode.child[currentChar] = new Node(currentNode.value + currentChar);
            }

            currentNode = currentNode.child[currentChar];
            currentNode.count++;
        }
        currentNode.end = true
    }

    search(string) {
        let currentNode = this.root;
        for(let i = 0; i <string.length ; i++) {
            const currentChar = string[i];
            if(currentChar == '?') return currentNode.count;
            if(currentNode.child[currentChar]){
                currentNode = currentNode.child[currentChar];
            } else {
                return 0;
            }
        }
        return 1;
    }
}


function solution(words, queries) {
    let len = new Array();
    let rLen = new Array();
    let results = new Array();

    for(let i = 0; i < words.length; i++) {
        if(len[words[i].length] == null) len[words[i].length] = new Trie();
        len[words[i].length].insert(words[i]);
    }

    for(let i = 0; i < words.length; i++) {
        if(rLen[words[i].length] == null) rLen[words[i].length] = new Trie();
        rLen[words[i].length].insert(words[i].split('').reverse().join(''));
    }

    for (let i = 0; i < queries.length; i++) {
        if(queries[i].startsWith('?')){
            queries[i] = queries[i].split('').reverse().join('');

            if(rLen[queries[i].length] == null) results.push(0);
            else results.push(rLen[queries[i].length].search(queries[i]));
        } else {
            if(len[queries[i].length] == null) results.push(0);
            else results.push(len[queries[i].length].search(queries[i]));
        }
    }
    return results;
}