프로그래머스: 가사 검색 - javascript(이진탐색, 그리디)

문제 출처 

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

프로그래머스

 

문제 풀이 

효율성을 생각하지 않는다면, 아래 코드가 간결할 수 있겠다. 

function solution(words, queries) {
    let answer = new Array(queries.length).fill(0)
    queries.forEach((query, idx) => {
       let q =  '^'+ query.replaceAll('?','.') + '$'
       let regex = new RegExp(q)
       let cnt = 0; 
       words.forEach(word => {
           if(word.match(regex)) cnt++
       })
        answer[idx] = cnt;     
    })
    return answer; 
}

실패코드 

filter, map, sort 등의 반복적인 사용으로 인해 성능이 저하됐다... 

이중 이진 탐색 방식을 적용하고, 불필요한 배열 복사를 피하는 방법을 생각해보자. 

function solution(words, queries) {
    let answer = []; 
    words.sort()
    queries.forEach((query, idx) => {
        let startWord = query.replaceAll('?','a') 
        let endWord = query.replaceAll('?','z')
        let arr = words.filter(el => el.length === query.length)
        if(query[0] === '?'){
           arr = arr.map(el => el.split('').reverse().join('')).sort()
           startWord= startWord.split('').reverse().join('')
           endWord= endWord.split('').reverse().join('')
        }
        let startIdx = binaryStart(arr, startWord)
        let endIdx = binaryEnd(arr, endWord)
        let amount = endIdx - startIdx
        answer.push(amount)
    })
    return answer; 
    
    //시작 idx 찾기 
   function binaryStart(arr, target){
       let start = 0; 
       let end = arr.length-1 
       while(start <= end){
           let mid = parseInt((start + end)/2)
           if(arr[mid] >= target){
               end = mid - 1; 
           }else{
               start = mid + 1
           }
       }
       return start 
   }   
    //포함하지 않는 idx 찾기 
   function binaryEnd(arr, target){
        let start = 0; 
        let end = arr.length - 1 
        while(start <= end){
            let mid = parseInt((start + end)/2)
            if(arr[mid] <= target){
                start = mid + 1 
            }else{
                end = mid - 1
            }
        }
       return start
    }
}

 

정답코드 1 

function solution(words, queries) {
    let answer = []; 
    const dictionary = {}
    const reverseDictionary = {}
    
    //words를 길이를 key, 값에 word를 넣자. 
    words.forEach((word) => {
        let len = word.length 
        if(!dictionary[len]){
            dictionary[len] = []
            reverseDictionary[len] = []
        }
        dictionary[len].push(word)
        reverseDictionary[len].push(word.split('').reverse().join(''))
    })
    
    //베열 정렬하기
    for(let value of Object.values(dictionary)){
        value.sort()
    }
    for(let value of Object.values(reverseDictionary)){
        value.sort()
    }
    
    queries.forEach((query, idx) => {
        let startWord = query.replaceAll('?','a') 
        let endWord = query.replaceAll('?','z')
        let len = query.length 
        let arr = []
        if(len === 0 || !dictionary[len]){
            answer.push(0); 
            return; 
        }
        if(query[0] === '?'){
            if(!reverseDictionary[len]){
                 answer.push(0); 
                 return 
            }
            arr = reverseDictionary[len]
            startWord = startWord.split('').reverse().join('')
            endWord = endWord.split('').reverse().join('')
        }else arr = dictionary[len]
       
        let startIdx = binaryStart(arr, startWord)
        let endIdx = binaryEnd(arr, endWord)
        let amount = endIdx - startIdx
        answer.push(amount)
        })
    return answer; 
    
    //시작 idx 찾기 
   function binaryStart(arr, target){
       let start = 0; 
       let end = arr.length-1 
       while(start <= end){
           let mid = parseInt((start + end)/2)
           if(arr[mid] >= target){
               end = mid - 1; 
           }else{
               start = mid + 1
           }
       }
       return start 
   }   
    //포함하지 않는 idx 찾기 
   function binaryEnd(arr, target){
        let start = 0; 
        let end = arr.length - 1 
        while(start <= end){
            let mid = parseInt((start + end)/2)
            if(arr[mid] <= target){
                start = mid + 1 
            }else{
                end = mid - 1
            }
        }
       return start
    }
}

정답코드 2

더 정리해봤다. 

function solution(words, queries) {
    let answer = []; 

    // 단어 길이별로 사전을 구축
    const wordDict = {};
    const reversedWordDict = {};

    words.forEach(word => {
        const len = word.length;

        if (!wordDict[len]) {
            wordDict[len] = [];
            reversedWordDict[len] = [];
        }

        wordDict[len].push(word);
        reversedWordDict[len].push(word.split('').reverse().join(''));
    });

    // 각 단어 리스트를 사전순으로 정렬
    for (let len in wordDict) {
        wordDict[len].sort();
        reversedWordDict[len].sort();
    }

    queries.forEach(query => {
        const len = query.length;

        if (!wordDict[len]) {
            answer.push(0);
            return;
        }

        let startWord = query.replaceAll('?', 'a');
        let endWord = query.replaceAll('?', 'z');
        let arr;

        if (query[0] === '?') {
            // 접두사가 '?'인 경우
            arr = reversedWordDict[len];
            startWord = reverseString(startWord);
            endWord = reverseString(endWord);
        } else {
            // 접미사가 '?'인 경우
            arr = wordDict[len];
        }

        let startIdx = binaryStart(arr, startWord);
        let endIdx = binaryEnd(arr, endWord);
        let amount = endIdx - startIdx;
        answer.push(amount);
    });

    return answer;

    // 시작 idx 찾기 (lower bound)
    function binaryStart(arr, target) {
        let start = 0;
        let end = arr.length;

        while (start < end) {
            let mid = Math.floor((start + end) / 2);
            if (arr[mid] >= target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    // 포함하지 않는 idx 찾기 (upper bound)
    function binaryEnd(arr, target) {
        let start = 0;
        let end = arr.length;

        while (start < end) {
            let mid = Math.floor((start + end) / 2);
            if (arr[mid] > target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    // 문자열 뒤집기
    function reverseString(str) {
        return str.split('').reverse().join('');
    }
}