[JS] 순위 검색

문제

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

프로그래머스

 

 

풀이

문제를 풀이할 때 Map 객체를 이용해 사람들의 입력 데이터를 key로, 점수를 value로 Map객체에 저장했다. 물론 같은 조건에 다른 점수를 갖는 사람들이 있을 수 있으니 배열에 추가하는 형식으로 진행했다.

 

이후 검색 조건에 맞는 사람들의 수를 구할 때 일반적인 탐색을 진행하게 되면 시간초과가 발생할 수 있으니 이진탐색 알고리즘을 이용해 해당 조건의 점수들 중 결과로 만족하는 값을 탐색하도록 하자.

 

코드

const makeMap = (infos) => {
  const map = new Map();

  for (let info of infos) {
    const [lan, job, exp, food, score] = info.split(' ');
    const key = `${lan}-${job}-${exp}-${food}`;
    if (map.has(key)) {
      map.set(key, [...map.get(key), +score]);
    }
    else {
      map.set(key, [+score]);
    }
  }

  for (const [key, val] of map) {
    map.set(key, map.get(key).sort((a, b) => a - b));
  }
  return map;
};

const makeQuery = (query) => {
  const result = [];
  const split = query.split(' and ');
  const lan = split[0] === '-' ? ['cpp', 'java', 'python'] : [split[0]];
  const job = split[1] === '-' ? ['frontend', 'backend'] : [split[1]];
  const exp = split[2] === '-' ? ['junior', 'senior'] : [split[2]];
  let [food, score] = split[3].split(' ');
  food = food === '-' ? ['pizza', 'chicken'] : [food];

  for (let l of lan) {
    for (let j of job) {
      for (let e of exp) {
        for (let f of food) {
          result.push([`${l}-${j}-${e}-${f}`, +score]);
        }
      }
    }
  }
  return result;
};

const binarySearch = (numArr, targetNum) => {
  let [lp, rp] = [0, numArr.length - 1];

  while (lp <= rp) {
    let mid = ~~((lp + rp) / 2);

    if (numArr[mid] === targetNum) {
      while (mid > 0 && numArr[mid - 1] === targetNum) mid--
      return mid;
    }

    if (numArr[mid] <= targetNum) {
      lp = mid + 1;
    }
    else rp = mid - 1;
  }
  return lp;
};

const solution = (info, query) => {
  const map = makeMap(info);
  const answer = query.map((e) => {
    const lists = makeQuery(e);
    let sum = 0;

    for (const [newQuery, newScore] of lists) {
      const list = map.get(newQuery);
      sum += list ? list.length - binarySearch(list, newScore) : 0
    }

    return sum;
  });

  return answer;
};