[programmers] Lv2. 순위 검색 | 조합, 이분탐색 | protect-me

protect-me·2021년 9월 11일

알고리즘 문제풀이 programmers Lv2

목록 보기

22/23

🕊 Link

Lv2. 순위 검색 Javascript
https://programmers.co.kr/learn/courses/30/lessons/72412

🧑🏻‍💻 Code(javascript)

function solution(info, query) {
  const answer = [];
  let map = {};

  function combination(infos, score, map, start) {
    let key = infos.join("");
    let value = map[key];

    if (value) {
      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(map, key, score) {
    let scoreArr = map[key];

    if (scoreArr) {
      let start = 0;
      let end = scoreArr.length;
      while (start < end) {
        let mid = Math.floor((start + end) / 2);

        if (scoreArr[mid] >= score) {
          end = mid;
        } else if (scoreArr[mid] < score) {
          start = mid + 1;
        }
      }
      return scoreArr.length - start;
    }
    else return 0

  }

  for (let i = 0; i < info.length; i++) {
    const infos = info[i].split(" ");
    const score = infos.pop();
    combination(infos, score, map, 0);
  }

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

  for (let i = 0; i < query.length; i++) {
    let queries = query[i].replace(/ and /g, "").split(" ");
    let score = Number(queries.pop());
    answer.push(binarySearch(map, queries[0], score));
  }

  return answer;
}