프로그래머스: 순위 검색 - javascript(조합, 이진탐색, 그리디)

문제 출처 

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

프로그래머스

정답 풀이 

와 진짜 기가막힌 쌈박한 ! 문제였다고 생각한다. 

이런 사고전환이 가능하다는 것을 알게 될 때 쾌감이 느껴진다. 

 

나는 정확성만 해결하는 방법만 떠올라서,,, 카카오가 원하는 사고는 뭐였을까? 들어가봤다. 

https://tech.kakao.com/posts/420

2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설 - tech.kakao.com

 

카카오가 의도한 아이디어를 활용하여 문제를 푸니, 시간 효율성까지 통과할 수 있었다 ! 

( 한번 읽고, 제가 작성한 글을 읽는다면 더 이해가 쉬울 것 같습니다용 )

 

info 배열의 크기는 1 이상 50,000 이하 

query의 배열 크기는 1 이상 100,000 이하다. 

만약 각 query마다 조건을 만족하는 info를 구한다면 시간 효율성에서 당연히 탈락이다. 

100,000 * 50,000 = 5,000,000,000  => 무려 50억의 연산을 해야한다. 

보통은 연산이 1억 이내 정도여야 하니, ! 이 방법은 옳지 않다. 

 

여기서 기가막힌 발상이 나오는데, 

미리 info 배열에서 조합을 구하는 것이다. 

예를 들어, "java backend junior pizza 150" 인 경우에 이런 map 객체를 생성할 수 있다. 

 

java = [150] //query조건이 java인 경우에 점수가 150인 사람이 있다는 뜻. 

backend = [150]

junior = [150]

pizza = [150]

java backend = [150] //query 조건이 java backend 인 경우에 점수가 150인 사람이 있다는 뜻. 

java  junior = [150]

...

java backend junior pizza = [150]

 

이렇게 하면, info 하나당 조합이 16개가 나온다. 

 

이렇게 세팅을 해준다면, 나중에 정리가 된 Map객체를 확인해보자. 

아래는 좀 잘렸는데, query는 보기도 전에, 이미 우리는 어떤 조건에 대하여 몇명이 만족하고 있는지 알 수 있는 상태가 된다. 

 

 

혹시 map 객체에서 'none'이라는 key를 발견하고(map 객체 맨 앞에 있음.) 의문을 품었다면,,  아주 예리하다. 

query가 만약 "- and - and - and - 150" 인 경우에 

모든 info들은 조건을 다 만족한 것이라고 할 수 있으니, 저렇게 세팅을 하나 해놨다. 

 

그리고 map 객체에 숫자를 다 넣고, 오름차순으로 정렬도 해놨다. 

난 미리 정렬 안하고, query에서 탐색할 때 정렬을 했더니 시간 초과가 났다. 

그러니 미리 하자. 

 

사실 이 정도면 다 푼거라고 할 수 있다. 

그러니 좀 더 힘을 내서 따라와보자 ~~ 

 

이제 대망의 query 탐색 시간 

query에서 and와 '-' 를 빼서 조건을 정리한다. 

- map 객체에서 해당 조건에 맞는 배열을 가져오고 

- 이진 탐색을 돌려준다. => score 이상인 사람들의 수를 찾기 위함임 !! 

 

급하게 마무리한 감이 있지만, 나머지는 코드와 주석을 보면서 충분히 이해할 수 있을 것이다. 

 

주석 처리 

function solution(info, query) {
    let answer = []
    
    let map = new Map(); 
    map.set('none', []) //어떤 조건도 없는 query 대비 모든 info의 점수를 다 넣어줄 것임. 
    
    info.forEach((info_per, idx) => {
       let infos = info_per.split(' ') 
       let score = Number(infos.pop()) //점수 
      
       map.get('none').push(score) //모든 사람이 다 해당됨 
       
       
       for(let i=1; i<=4; i++){//각 info의 조합을 만들어줌 
        let results = getCombination(infos, i)
        results.flatMap((re) => {
            re = re.join('')
            if(!map.has(re)) map.set(re, []) //조건이 map 객체에 없다면 새로 생성 
            map.get(re).push(score) //조건에 score를 넣어준다. 
        })
       }
    })
    
    for(let values of map.values()){ //map 객체의 모든 배열 값을 오름차순으로 정렬
        values.sort((a,b) =>a-b)
    }
    
    //query를 탐색하면서 조건에 맞는 사람 수 구하자. 
    query.forEach((qu, idx) => { 
       let per_query =  qu.split(/ and |-/g)
       let real_query = per_query.join('').match(/\D+/g)[0].replace(/\s+/,'') //조건 정리
       let score = Number(per_query.join('').match(/\d+/g)[0]) //점수 
       if(real_query.length === 0) check('none', score) //점수 조건만 있을 경우
       else if(!map.has(real_query)) answer.push(0) //조건이 map 객체에 없다는건 아무도 조건 만족하지 못한다는 뜻
       else check(real_query,score) //조건에 map 객체에 있을 경우 
    })
    
    return answer; 
    
    //해당 map의 key 값 받고, 이진탐색 함수 돌려서 answer에다가 해당하는 숫자 push 할 거임. 
    function check(key, num){
        let arr = map.get(key) //조건에 해당하는 배열 값
        let idx = binarySearch(arr, num) 
        answer.push(arr.length - idx) //해당하는 점수 이상인 사람 수 answer에 push 
    }
        
    //이진탐색은 해당 target 점수 이상의 시작점 idx를 return 할 것임.     
    function binarySearch(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
            if(arr[mid] < target) start = mid + 1
        }
        return start
    }
    
    function getCombination(arr, selectNum){
        let results = [];
        if(selectNum === 1) return arr.map(v => [v])
        arr.forEach((fixed, idx, origin) => {
            const rest = origin.slice(idx + 1)
            const combinations = getCombination(rest, selectNum - 1)
            const attached = combinations.map((combi) => [fixed, ...combi])
            results.push(...attached)
        })
        return results
    }
}

 

정답 코드 

function solution(info, query) {
    let answer = []
    
    let map = new Map(); 
    map.set('none', [])
    
    info.forEach((info_per, idx) => {
       let infos = info_per.split(' ')
       let score = Number(infos.pop())
       map.get('none').push(score)
       for(let i=1; i<=4; i++){
        let results = getCombination(infos, i)
        results.flatMap((re) => {
            re = re.join('')
            if(!map.has(re)) map.set(re, [])
            map.get(re).push(score)
        })
       }
    })
    
    for(let values of map.values()){
        values.sort((a,b) =>a-b)
    }
    
    query.forEach((qu, idx) => {
       let per_query =  qu.split(/ and |-/g)
       let real_query = per_query.join('').match(/\D+/g)[0].replace(/\s+/,'')
       let score = Number(per_query.join('').match(/\d+/g)[0])
       if(real_query.length === 0) check('none', score)
       else if(!map.has(real_query)) answer.push(0)
       else check(real_query,score)
    })
    
    return answer; 
    
    //해당 map의 key 값 받아서 이진탐색 함수 돌려서 answer에다가 해당하는 숫자 push 할 거임. 
    function check(key, num){
        let arr = map.get(key)
        let idx = binarySearch(arr, num)
        answer.push(arr.length - idx)
    }
        
    function binarySearch(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
            if(arr[mid] < target) start = mid + 1
        }
        return start
    }
    
    function getCombination(arr, selectNum){
        let results = [];
        if(selectNum === 1) return arr.map(v => [v])
        arr.forEach((fixed, idx, origin) => {
            const rest = origin.slice(idx + 1)
            const combinations = getCombination(rest, selectNum - 1)
            const attached = combinations.map((combi) => [fixed, ...combi])
            results.push(...attached)
        })
        return results
    }
}