[이진 탐색][프로그래머스] 순위 검색

     

목차

 

문제

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

프로그래머스

 

 

문제 구현 방향

각 종류의 개수가 적어 24가지의 경우를 만든후 map에 넣어 탐색하면 될 것 같아 

모든 경우를 조합하여 탐색하였다.

 

 

 

코드 구현

let lang = ["cpp", "java", "python"];
let type = ["backend", "frontend"];
let year = ["junior", "senior"];
let food = ["chicken", "pizza"];
let m = new Map();
function solution(info, query) {
    var answer = [];
    let arr = [];
    let str = "";
    let cnt = 0;

    combi(arr, str, cnt);

//각 조합에 대해 배열 담아주기
    for (let ifo of info) {
        let splt = ifo.split(" ");
        let num = Number(splt.pop());
        let str = splt.join("");
        if (m.get(str.trim()).length >= 1)
            m.set(str, [...m.get(str.trim()), num]);
        else m.set(str, [num]);
    }
    
    //이진 탐색을 위한 정렬
    for (let [key, value] of m) {
        value.sort((a,b)=>a-b);
        m.set(key, value);
    }

    for (let qry of query) {
        let cnt = 0;
        let str = "";
        let target = [];
        let splt = qry.split(" and ");
        let num = Number(splt[splt.length - 1].split(" ")[1]);
        splt[splt.length - 1] = splt[splt.length - 1].split(" ")[0];
        finding(splt, cnt, str, target);
        let sum =0;
        for(let tg of target){
            let M = m.get(tg);
            let idx = binarySearch(0, M.length-1, M, num);
            if(isFinite(idx)){
                sum +=M.length-idx;
            }
         
        }
        answer.push(sum);
    }
    return answer;
}

function binarySearch(str, end, arr, tg) {
    let ans = Infinity;
    while (str <= end) {
        let mid = Math.floor((str + end) / 2);
        if (arr[mid] >= tg) {
            end = mid - 1;
            ans =mid;
        } else {
            str = mid + 1;
        }
    }
    return ans;
}

function finding(qry, cnt, str, target) {
    let qr = qry[cnt];
    if (cnt === 4) {
        target.push(str);
        return;
    }
    if (qr !== "-") {
        let nstr = str + qr;
        finding(qry, cnt + 1, nstr, target);
        return;
    }
    if (qr === "-" && cnt === 0) {
        for (let i = 0; i < 3; i++) {
            let nstr = str + lang[i];
            finding(qry, cnt + 1, nstr, target);
        }
    } else if (qr === "-" && cnt === 1) {
        for (let i = 0; i < 2; i++) {
            let nstr = str + type[i];
            finding(qry, cnt + 1, nstr, target);
        }
    } else if (qr === "-" && cnt === 2) {
        for (let i = 0; i < 2; i++) {
            let nstr = str + year[i];
            finding(qry, cnt + 1, nstr, target);
        }
    } else if (qr === "-" && cnt === 3) {
        for (let i = 0; i < 2; i++) {
            let nstr = str + food[i];
            finding(qry, cnt + 1, nstr, target);
        }
    }
}

function combi(arr, str, cnt) {
    if (cnt === 4) {
        m.set(str.trim(), []);
        return;
    }
    if (cnt === 0) {
        for (let i = 0; i < 3; i++) {
            let nstr = str + lang[i];
            combi(arr, nstr, cnt + 1);
        }
    } else if (cnt === 1) {
        for (let i = 0; i < 2; i++) {
            let nstr = str + type[i];
            combi(arr, nstr, cnt + 1);
        }
    } else if (cnt === 2) {
        for (let i = 0; i < 2; i++) {
            let nstr = str + year[i];
            combi(arr, nstr, cnt + 1);
        }
    } else if (cnt === 3) {
        for (let i = 0; i < 2; i++) {
            let nstr = str + food[i];
            combi(arr, nstr, cnt + 1);
        }
    }
}