[LeetCode] search-suggestions-system

문제링크

Search Suggestions System - LeetCode

 

주어진 문자열 products의 요소 중 주어진 검색 단어 searchWord의 첫 단어, 첫 단어 + 두 번째 단어, 첫 단어 + 두번째 단어 + 세번째 단어... 모든 단어 와 일치하는 단어들을 찾아 사전 순으로 정렬하고 앞 3단어를 추출하는 문제이다.
(ex. products = ['a', 'abc', 'abd, 'eed', 'abcd'], searchWord = "abcde" 일때
output은 [['a', 'abc', 'abcd'], ['abc', 'abcd', 'abd'], ['abc', 'abcd'], ['abcd'], []] 이 출력된다.
(output[0]에선 ['a', 'abc', 'abcd', 'abd']가 검색되지만 3개를 잘라서 'abd'가 잘린 것이다.))

접근 방법

먼저 output은 무조건 searchWord의 길이만큼 2차원 배열이 된다.

그리고 주어진 searchWord의 단어를 하나씩 추가하며 검색해야한다.

여기서 정규식을 사용하여 접근하였다.

for(let i = 0; i < searchWord.length; i++){
    let regWord = new RegExp(searchWord.slice(0,i+1))
    console.log(regWord)
}
/*
출력
/a/
/ab/
/abc/
/abcd/
/abcde/
*/​

그리고 모든 products의 요소들을 filter 하며 정규식으로 만든 regWord와 match될때만 output 배열에 push 하였다.


배운 점

1.

// 처음 2차원 배열을 생성한 방법
let output = new Array(searchWord.length).fill([])

// 고친 방법
let output = Array.from({length : searchWord.length}, () => [])​

 

처음 방법대로 2차원 배열을 생성하면 fill([])의 배열들이 모두 같은 주소를 갖게 된다.
때문에 output[0]에 임의의 값을 push하면 output의 모든 []에 값이 같이 들어가게 된다.

때문에 Array.from 방식으로 2차원 배열을 생성하였다.

 
2.

// 처음 정규식으로 filter한 방법
products.filter(product => {
    if(product.match(regWord)){
        output[i].push(product)
    }
})

// 고친 방법
products.filter(product => {
    if(product.match(regWord)){
        if(product.match(regWord).index === 0) output[i].push(product)
    }
})​

문제의 조건은 처음 단어부터 같은 단어만 요구한다. (product : "mouse", searchWord : "mo" 일 경우만 true)
하지만 처음 방식은 (product : "toomos", searchWord : "mo" 일 경우에도 true이므로 값을 반환한다.)

그래서 match 값에 index 번호가 0일 경우만 push하도록 바꾸었다.

하지만 이 코드는 너무 소요 시간이 오래 걸린다.

9.5 %..

약간 비효율적이라 생각한 부분을 고쳤다.
1. sort()
2. slice()

// 매번 sort()를 하는게 비효율적이라 생각하여 미리 한번 처리하니 속도가 올랐다.
products.sort();

// 모두 구해서 3개를 자르는 것도 비효율적이라 생각되어
output[i] = output[i].slice(0,3)

// push 조건에 output[i].length < 3일때만 push 하도록 조건을 추가하여 속도를 올렸다.
if(product.match(regWord).index === 0 && output[i].length < 3) {
	output[i].push(product)
    }

아직도 낮다.. 접근 방향이 잘못된듯하다.

 

// 수정한 코드
var suggestedProducts = function(products, searchWord) {
    products.sort();
    let output = Array.from({length : searchWord.length}, () => [])
    
    for(let i = 0; i < searchWord.length; i++){
        let regWord = new RegExp(searchWord.slice(0,i+1))
        
        products.filter(product => {
            if(product.match(regWord)){
                if(product.match(regWord).index === 0 && output[i].length < 3) output[i].push(product)
            }
        })
    }
    
    return output
};

// 수정 전 코드

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function(products, searchWord) {
    let output = Array.from({length : searchWord.length}, () => [])
    
    for(let i = 0; i < searchWord.length; i++){
        let regWord = new RegExp(searchWord.slice(0,i+1))
        
        products.filter(product => {
            if(product.match(regWord)){
                if(product.match(regWord).index === 0) output[i].push(product)
            }
        })
        
        output[i] = output[i].sort().slice(0,3)
    }
    
    return output
};