[JS] 순위 검색

쿼리문을 활용해서 정보들을 빠르게 가져와야 하는 문제였다.

 

Map자료형을 활용해서 해결하였다. 정보를 입력할때 

 

언어-유형-기간-음식 을 하나의 key로 처리하도록 형식을 만들어서 입력해줬고, 해당 키가 있는경우에는 score를 리스트에 추가해주었다.

 

 

즉, 데이터를 입력받으면 아래와 같이 되야한다.

 

 

이어서 쿼리문을 입력받아야 하는데  ' - ' 가 오는경우에는 그 언어의 모든 경우의수를 만들어주는 함수를 만들었다.

 

만약 아래 사진처럼 - and - and - and chicken 100이라면, 검색해야하는 쿼리문들을 모두 찾아주었다.

 

 

 

어차피 Map자료형으로 만들었기 때문에 Map자료형에 있는 저 값들 중에서 점수보다 높은 값들의 개수만 알면 된다.

 

 

처음에는 filter함수를 활용해서 해결했는데 효율성 테스트에서 걸리고 말았다.

 

 

 

개수를 찾는 부분의 시간을 줄이기 위해서 이진탐색을 통해서 가져왔다. 이때 주의해야 할 점이 이진탐색으로 idx를 가져올때 중복된 값이 있을때 가장 왼쪽의 idx를 가져오게 해야한다.

 

 

[ 50 60 70 100 100 100 100 150 ] 이렇게 리스트가 존재하고, 만약 100 이상을 가져온다면

 

우리가 원하는 개수를 세기 위해서는 4를 가져와야 하지만, 이진탐색을 그대로 적용하면 5를 가져오게 된다. 따라서 이진탐색을 사용할때 가장 왼쪽의 idx값을 가져오도록 설정해주었다.

 

 

 

 

 

function solution(info, queries) {
    const dataBase = new Map()
    
    //데이터베이스에 넣기
    for (const str of info) {
        const [lang,type,period,food,score] = str.split(" ")
        const key = `${lang}-${type}-${period}-${food}`
        
        if (dataBase.get(key)) dataBase.set(key,[...dataBase.get(key), +score])
        else dataBase.set(key,[+score])
    }
    
    for (const [key,val] of dataBase){
        dataBase.set(key,val.sort((a,b) => a-b))
    }
    
    const seperateQuery = (query) => {
        
        let [lang,type,period,last] = query.split(" and ")
        let [food,score] = last.split(" ")
        
        lang = lang==="-" ? ['cpp','java','python'] : [lang]
        type = type==="-" ? ['backend','frontend'] : [type]
        period = period==="-" ? ['junior','senior'] : [period]
        food = food==="-" ? ['chicken','pizza'] : [food]
        
        let ret = []
        for (const la of lang){
            for (const ty of type) {
                for (const pe of period) {
                    for (const fo of food) {
                        ret.push([`${la}-${ty}-${pe}-${fo}`,+score])
                    }
                }
            }
        }
        return ret
    }
    
    const binarySearch = (list,num) => {
        let [left,right] = [0,list.length-1]
        
        while (left <= right) {
            let mid = ~~((left + right) / 2)
            if (list[mid] === num) {
                while (mid>0 && list[mid-1]===num) mid --
                return mid
            }
            
            if (list[mid] > num) right = mid-1
            else left = mid+1
        }
        return left
    }
    
    
    const ret = queries.map(query =>{
        const newQueryList = seperateQuery(query)
        let sum_ = 0
        
        for (const [newQuery,score] of newQueryList){
            
            const numList = dataBase.get(newQuery)
            sum_ += numList ? numList.length-binarySearch(numList,score) : 0
        }
        
        return sum_
    })
    
    return ret
    
}