🔎 순위 검색

❓ 문제링크

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

📄 제출 코드

function solution(info, query) {
    var answer = [];
    const map = {};
    let info_len = info.length;
    let query_len = query.length;
    
    function combination(cnt, key, arr, score) {
        if (cnt == 4) {
            !map[key] ? map[key] = [score] : map[key].push(score);
            return;
        }
        combination(cnt + 1, key + arr[cnt], arr, score)
        combination(cnt+1, key+"-",arr,score)
    }

    for (let i = 0; i < info_len; i++) {
        const arr = info[i].split(" ");
        const score = Number(arr.pop());
        combination(0, "", arr, score);
    }

    for (let key in map) {
        map[key] = map[key].sort((a, b) => a - b);
    }

    for (let i = 0; i < query_len; i++) {
        const arr = query[i].replace(/ and /g, " ").split(" ");
        const score = parseInt(arr.pop());
        const key = arr.join("");
        const scoreArray = map[key];
        if (scoreArray) {
            let left = 0;
            let right = scoreArray.length;

            while (left < right) {
                const mid = parseInt((left + right) / 2);
                (scoreArray[mid] >= score) ? right = mid : left = mid + 1;
            }
            answer.push(scoreArray.length - left);
        } else {
            answer.push(0);
        }
    }
    return answer;
}
let info = ["java backend junior pizza 150", "python frontend senior chicken 210", "python frontend senior chicken 150", "cpp backend senior pizza 260", "java backend junior chicken 80", "python backend senior chicken 50"];
let query = ["java and backend and junior and pizza 100", "python and frontend and senior and chicken 200", "cpp and - and senior and pizza 250", "- and backend and senior and - 150", "- and - and - and chicken 100", "- and - and - and - 150"];
console.log(solution(info, query));

처음에 하나하나 조건에 맞게 구현하면서 풀어봐야겠다고 생각했다.
그래서 시간초과 날거 같긴했지만, 답은 맞추는데 성공했고, 효율성에서 다 시간 초과가 발생했다. 그래서 어떻게 줄이지 한참고민하다가 결국 다른사람들의 코드를 참고했다.

위 코드는 조합과 2분탐색을 이용한 방법이다.

• info를 순회하면서 '-'가 들어갈 수 있는 조합을 모두 구하고 map에 저장.
• 그 다음 map에 있는 property의 value는 배열 형태로 저장.

function combination(cnt, key, arr, score) {
  if (cnt == 4) {
    !map[key] ? map[key] = [score] : map[key].push(score);
    return;
  }
  combination(cnt + 1, key + arr[cnt], arr, score)
  combination(cnt+1, key+"-",arr,score)
}

for (let i = 0; i < info_len; i++) {
  const arr = info[i].split(" ");
  const score = Number(arr.pop());
  combination(0, "", arr, score);
}

• value를 정렬하고, 이분 탐색.

for (let key in map) {
  map[key] = map[key].sort((a, b) => a - b);
}

• map[key]에 값이 배열이 없다면 검색에 맞는 조건의 사람이 없다는 뜻. 0을 넣어줌.

for (let i = 0; i < query_len; i++) {
  const arr = query[i].replace(/ and /g, " ").split(" ");
  const score = parseInt(arr.pop());
  const key = arr.join("");
  const scoreArray = map[key];
  if (scoreArray) {
    let left = 0;
    let right = scoreArray.length;

    while (left < right) {
      const mid = parseInt((left + right) / 2);
      (scoreArray[mid] >= score) ? right = mid : left = mid + 1;
    }
    answer.push(scoreArray.length - left);
  } else {
    answer.push(0);
  }
}

📄 이전 코드

function solution(info, query) {
    var answer = [];
    let info_len = info.length;
    let query_len = query.length;
    
    for (let i = 0; i < query_len; i++) {
        let cnt = 0;
       
        let condition = query[i].split(" and ");
        let tmp = condition.pop();
        // console.log(tmp);
        let last = tmp.split(" ");
        // console.log(last);
        condition.push(last[0]);
        condition.push(parseInt(last[1]));
        // console.log(`condition : ${condition}`);
        
        for (let j = 0; j < info_len; j++) {
            let info_condition = info[j].split(" ");
            let i_tmp = info_condition.pop();
            info_condition.push(parseInt(i_tmp));        
            let chk = 0;
            
            // console.log(`info_condition : ${info_condition}`);
            for (let k = 0; k < info_condition.length; k++) {
                if (condition[k] == '-') {
                    chk++;
                    // console.log(`chk : ${chk}`);
                }
                else if (info_condition[k] == condition[k]) {
                    chk++;
                    // console.log(`chk : ${chk}`);
                    
                }
                else if (info_condition[k] != condition[k]) {
                    break;
                }
                if (chk == 4) {
                    k++;
                    if (info_condition[k] >= condition[k]) {
                        cnt++;
                        // console.log(`before : ${cnt}`)
                    }
                    break;
                }
            }
        }
        // console.log(`after : ${cnt}`)
        // console.log();
        answer.push(cnt);
    }
    return answer;
}

let info = ["java backend junior pizza 150", "python frontend senior chicken 210", "python frontend senior chicken 150", "cpp backend senior pizza 260", "java backend junior chicken 80", "python backend senior chicken 50"];
let query = ["java and backend and junior and pizza 100", "python and frontend and senior and chicken 200", "cpp and - and senior and pizza 250", "- and backend and senior and - 150", "- and - and - and chicken 100", "- and - and - and - 150"];
console.log(solution(info, query));

📘 참고

https://gooweon.tistory.com/175