Portfolio

풀이

은찬


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;
}

재영


class Node {
  constructor(value = "") {
    this.value = value;
    this.childrenLengthCounts = {};
    this.children = new Map();
  }
}

class Trie {
  constructor() {
    this.root = new Node(); // frodo => f -> r -> o -> d -> o 
  }

  insert(chars) {
    let currentNode = this.root;

    for (const char of chars) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new Node(currentNode.value + char))
      }
      currentNode.childrenLengthCounts[chars.length] = currentNode.childrenLengthCounts[chars.length] 
        ? currentNode.childrenLengthCounts[chars.length] + 1 
        : 1;
      currentNode = currentNode.children.get(char);
    }

  }

  has(chars) {
    let currentNode = this.root;

    for (const char of chars) {
      if (!currentNode.children.has(char)) {
        return false;
      }

      currentNode = currentNode.children.get(char);
    }
    return true;
  }

  getCorrespondingLyricsCount(chars, lyricLength) {
    let currentNode = this.root;

    for (const char of chars) {
      if (!currentNode.children.has(char)) return 0;

      currentNode = currentNode.children.get(char);
    }

    return currentNode.childrenLengthCounts[lyricLength] ? currentNode.childrenLengthCounts[lyricLength] : 0;
  }
}

const solution = (words, queries) => {
  const result = [];

  const lyricsTrie = new Trie(); // front trie
  const reversedLyricsTrie = new Trie(); // back trie 
  
  words.forEach(word => {
    lyricsTrie.insert(word);
    reversedLyricsTrie.insert([...word].reverse().join(''));
  })

  queries.forEach(query => { // fr??? -> argument - (fr, 5)
    const length = query.length; // cashing
    const check = query.startsWith('?'); // 내가 backtrie로 접근해야 되니?
    const queryArr = check ? [...query].reverse() : [...query];
    
		while (queryArr[queryArr.length - 1] === '?') {
      queryArr.pop(); // ?를 지워주는 작업
    }
    
    result.push((check ? reversedLyricsTrie : lyricsTrie).getCorrespondingLyricsCount(queryArr.join(''), length))
  })

  return result;
}

(() => {
  const words = ["frodo", "front", "frost", "frozen", "frame", "kakao"];
  const queries = ["fro??", "????o", "fr???", "fro???", "pro?"];
  console.log(solution(words, queries));
})();

가사검색

풀이