[프로그래머스] 순위 검색 javascript ⭐

 

2021.08.17

문제명 : 2021 KAKAO BLIND RECRUITMENT 순위 검색

사용언어 : Javascript

개발 시간 : 120분 + 다른 사람 풀이 60분

 

코딩테스트 연습 - 순위 검색

 

📋 문제 설명

이 문제의 핵심은 조합과 이분탐색입니다.

주어진 info 배열이 가질 수 있는 조합을 모두 구하고

이분탐색을 이용해 query 배열의 조건에 맞는 갯수를 구하는 것입니다.

 

---

이분 탐색의 간단한 예시를 먼저 보고 갑시다.

 

1 2 3 4 5 6라는 값에서 6을 찾고자 한다면

 

배열의 중간에 위치한 3이라는 값과 6을 비교합니다.

 

6은 3보다 크므로, 이제 3의 왼쪽에 위치하는 값들은 탐색할 필요가 없으므로

(어차피 3 왼쪽에 있는 수들은 3보다 작기 때문입니다)

 

3의 오른쪽에 있는 값들을 대상으로 탐색을 다시 시도합니다.

 

이제 4 5 6이 남았으므로, 다시 중간값인 5와 찾고자 하는 대상인 6를 비교합니다.

 

6은 5보다 크므로, 5의 오른쪽에 있는 값들을 대상으로만 탐색을 다시 시도합니다.

 

이제 6만이 남았는데 6과 6을 비교하면, 값이 일치하므로 탐색을 종료합니다.

출처: https://satisfactoryplace.tistory.com/39

 

---

 

우선 조합을 통해서 - 를 다 넣어줍니다.

 

예를 들어, 

java backend junior pizza 150 이 입력으로 들어왔다고 칩시다. 

 

- backend junior pizza 150

java   -  junior pizza 150

java backend - pizza 150

java backend junior - 150

.

.

.

- - - - 150 

이런식으로 -를 넣을 수 있는 곳을 조합으로 찾아 모두다 150을 넣어줍니다.

 

출처 : https://dkwjdi.tistory.com/224

---

 

📢 입출력 예

 

🔑 문제 풀이

// 정확성 테스트 success
// 효율성 테스트 success
function solution(info, query) {
    var answer = [];
    let map = {};
    
    function combination(infos, score, map, start){
        let key = infos.join("");  // 키 값으로 쓸거 합쳐주기
        let value = map[key];      // 값 있는지 없는지 확인해주기
    
        if(value){ // 값이 있으면 push
            map[key].push(score);
        }else{ // 값이 없으면 프로퍼티 만들어주기
            map[key] = [score];
        }
        
        // -를 이용해 조합 만들기
        for(let i=start; i<infos.length; i++){
            let combiArr = [...infos]; // 전개연산자 ...
            combiArr[i] = '-';
            
            combination(combiArr, score, map, i+1);
        }
    }
    
    
    // 이분탐색
    function binarySearch(map2, key2, score2){
        let scoreArr = map2[key2];
       
        if(scoreArr){
       
            var start = 0;
            var end = scoreArr.length;
            
            while(start < end){
                var mid = Math.floor((start+end)/2);
                
                if(scoreArr[mid] >= score2){ // 현재 가르키는 값보다 내가 찾는 값이
                    end = mid;
                }else if(scoreArr[mid] < score2){
                    start = mid + 1;
                }
            }
            
            return scoreArr.length - start;
        }
        else return 0
        
    }
    
    
    
    // 1. -로 가능한 모든 조합 만들기
    for(let i=0; i<info.length; i++){
        let infos = info[i].split(" ");
        let score = infos.pop();
        
        combination(infos, score, map, 0);
    }
    
    // 2. 이분탐색을 위해 정렬
    for(let key in map){
        map[key].sort((o1, o2) => o1 - o2);
    }
    
    // 3. 이분탐색 실행
    for(let i=0; i<query.length; i++){
        let querys = query[i].replace(/ and /g, "").split(" ");
        let score = Number(querys.pop());
      
        answer.push(binarySearch(map, querys.join(""), score));
    }
    
    return answer;
}

 

// 정확성 테스트 success
// 효율성 테스트 fail
function solution(info, query) {
    var answer = [];
    var arr1 = [];
    var arr2 = [];
    
    for(var i=0; i<info.length; i++){
        arr1.push(info[i].split(' '));
    }
    for(var i=0; i<query.length; i++){
        arr2.push(query[i].replace(/and /gi,'').split(' '));
    }
    
    
    for(var i=0; i<arr2.length; i++){
        var cnt = 0;
        for(var j=0; j<arr1.length; j++){
            for(var k=0; k<4; k++){   
                if(arr2[i][k] == arr1[j][k] || arr2[i][k] == '-'){
                    if(k==3 && arr2[i][4]*1 <= arr1[j][4]*1){
                        cnt++;
                    }
                }else{
                    break;
                }
            }
        }
        answer.push(cnt);
    }
    return answer;
}

 

🔔 새로 알게 된 점

2단계가 맞나 싶을 정도로 난이도가 높게 느껴졌다.

첫 시도때는 점수를 제외한 조건들만 차례대로 비교하면서 충족할 경우에만 점수를 비교하였다.

이렇게 풀면 정답이긴 하나, 효율성 테스트에서 fail이 뜬다.

for문이 중첩되면서 타임아웃 에러가 나는 듯 하다.

 

다른 사람의 풀이를 참조하니 이분탐색을 이용하지 않으면 통과할 수 없는 문제같다.

조합, 이분탐색, 프로퍼티 등을 공부하고 알고리즘을 이해하는 것이 중요할 듯 하다.

 

프로퍼티 관련 : https://opentutorials.org/module/3989/26100