kakao2021 순위 검색 javascript

shleecloud·2022년 3월 15일

Algorithm

목록 보기

14/16

들어가며

2021 카카오 문제 중 하나다. 레벨 2라고 되어있는데 전혀 2같지가 않다. 하나의 문제에 두 개의 알고리즘을 적용해야 풀린다. 하나 하나는 레벨2라고 생각하면 납득이 가...나? 어려웠다. 특히 검색은 효율성이 높은 이분탐색을 사용해야 된다.

이 포스팅은 오답노트다. 내가 풀어보고 효율성에서 실패해서 쓴다. 한동안 이렇게 막혀서 고생한 문제가 없었는데 역시 카카오다. 숙제거리를 던져주는구나.

오답노트

내가 처음 풀었을 때는 단순하게 접근해서 매번 사용자를 찾아서 검사하는 로직으로 구현했다. info 배열의 크기는 최대 50000이고 query 배열의 크기는 최대 100000이다. 딱 봐도 시간이 초과된다.

왜 이렇게 안일하게 했을까. 문제를 접근하기 전에 미리 최악의 경우를 계산하고 적절한 알고리즘을 도입하는 훈련을 해야겠다고 다시 한 번 생각했다. 다 구현해놓고 뭉게는 일은 절대 있어서는 안된다. 요즘은 시간을 정해놓고 문제푸는 연습을 철저하게 하는데 설계 단계에서 실패하면 아무리 열심히 구현해도 답이 없다.

이번 문제는 ‘-’, 즉 정해지지 않은 값까지 고려해야 됐다. 이럴 경우 계수정렬과 비슷하게 모든 경우의 수에 맞게 점수를 할당하는게 정답이었다. 효율성을 끌어올리기 위해서 여기까지는 생각이 미치지 못했다.

이진 탐색을 할 때도 어떻게 조건문을 설정하냐에 따라 내가 찾는 값을 초과하는 인덱스를 찾을 수도, 이하인 인덱스를 찾을 수도 있었다. 여기서도 꽤 해맸다.

해설

쿼리에서 ‘-’ 으로 사용자를 찾을 수 있다. 그 경우의 수까지 모두 점수를 할당해서 쿼리가 들어오면 곧바로 쿼리에 맞는 key를 가진 점수 배열에서 검색하게 된다. 이럴 경우 초기 구축은 시간이 걸리지만 쿼리가 늘어나도 효율성을 유지할 수 있다. 점수 배열에선 이분 탐색을 사용한다. 그러려면 모든 경우의 수에 대해 정렬 해야된다. 그래도 쿼리가 워낙 많으니 정렬하는게 효율이 좋다.
정렬 후에는 쿼리가 있는지 확인하고 이진 탐색을 실행한다.

function solution(info, query) {
  // * 조합 만드는 함수 선언
  function getCombination(arr, score, map, start) {
    const key = arr.join('');
    if (Array.isArray(map[key])) map[key].push(score);
    else map[key] = [score];

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

  // * 이분 탐색 함수 선언
  function binarySearch(arr, score) {
    // 쿼리 결과가 없을 경우 예외 처리
    if (!arr) return 0;
    let left = 0;
    let right = arr.length;
    while (left < right) {
      // let mid = left + Math.floor((right - left) / 2);
      let mid = Math.floor((left + right) / 2);
      // ! 초과로 구할 경우의 수식.
      // ! 조건문으로 미만과 초과를 구분할 수 있다.
      // if (arr[mid] > score) right = mid;
      // else left = mid + 1;
      if (arr[mid] >= score) right = mid;
      else left = mid + 1;
    }
    // console.log(arr, score, left, right);
    return arr.length - left;
  }

  // * 조합 만들기
  const map = {};
  for (let i = 0; i < info.length; i++) {
    const infos = info[i].split(' ');
    const score = infos.pop();
    getCombination(infos, score, map, 0);
  }

  // * 조합 내의 점수 배열 정렬
  for (let key in map) map[key].sort((a, b) => a - b);

  // * 점수 찾기
  const result = [];
  for (let i = 0; i < query.length; i++) {
    let queryString = query[i].replace(/ and /g, '').split(' ');
    let queryScore = Number(queryString.pop());
    queryString = queryString.join('');
    let scoreIdx = binarySearch(map[queryString], queryScore);
    result.push(scoreIdx);
    // if (Array.isArray(map[queryString])) {
    //   let scoreCount = map[queryString].length - scoreIdx;
    //   result.push(scoreCount);
    // } else result.push(0);
  }

  return result;
}

const 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',
];
const querys = [
  '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, querys));