프로그래머스) 순위 검색(조합, 이진 탐색, Map vs Object)

-문제 사이트

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

프로그래머스

코드

function getCombination(arr, score, map, start) {
  let key = arr.join("");
  Array.isArray(map[key]) ? map[key].push(score) : (map[key] = [score]);

  for (let i = start; i < arr.length; i++) {
    let temp = [...arr];
    temp[i] = "-";
    getCombination(temp, score, map, i + 1);
  }
}

function binarySearch(arr, target) {
  if (!arr) return 0;

  let left = 0,
    right = arr.length;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);

    if (parseInt(arr[mid]) >= target) right = mid;
    else left = mid + 1;
  }

  return arr.length - left;
}

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

  let user = {};
  info.map((i) => {
    let temp = i.split(" ");
    let score = temp.pop();

    getCombination(temp, score, user, 0);
  });

  [...Object.entries(user)].map((i) => {
    user[i[0]] = i[1].sort((a, b) => a - b);
  });

  query.map((req) => {
    let arr = req.split(" and ");
    let temp = arr.pop().split(" ");
    let score = temp.pop();
    arr.push(...temp);

    answer.push(binarySearch(user[arr.join("")], score));
  });

  return answer;
}

해결 방법

이 문제를 풀기 위해서는 조합, 이진 탐색에 대해 이해하고 있어야했다. 처음 문제를 풀었을때 정확성은 다 맞았지만 효율성은 0점이었다. 효율성이 제일 중요하다고 생각하는데 이 부분이 0점이라서 많이 반성을 했다. 결국 이 문제를 구글링해서 다른 사람의 답을 보고 이해를 한 다음 내 풀이로 풀어봤다. 원리는 이해를 했지만 나는 Map에다가 데이터를 저장해서 또 효율성 문제가 발생했다.

Map vs Object

-참고 사이트

https://medium.com/@wdjty326/javascript-es6-map-vs-object-performance-%EB%B9%84%EA%B5%90-7f98e30bf6c8

JavaScript ES6 Map vs Object Performance 비교

위에서 말했듯이 Map으로 문제를 풀었을 때 시간 초과가 났다.

구글링으로 찾아보니까 Map은 set하는 것이 Object보다 시간이 오래 걸리는 것을 알았다. 반면 key를 기준으로 값을 찾는 것은 Map의 get이 더 빠른 것을 알았다. 

결론을 말하면 잦은 데이터 갱신과 적은 데이터 출력은 Object가 유용하고, 데이터 갱신과 많은 데이터 출력은 Map이 유용하다.

 

-문제 풀이 참고 블로그

https://velog.io/@shleecloud/kakao2021-%EC%88%9C%EC%9C%84-%EA%B2%80%EC%83%89-javascript

kakao2021 순위 검색 javascript