2021 KAKAO BLIND RECRUITMENT) 순위 검색 - Javascript 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/72412?language=javascript 

프로그래머스

 

문제에서는 정확성과 효율성 테스트가 각각 있기 때문에 입력으로 주어진 배열이 굉장히 클 때 어떻게 효과적으로 탐색을 할지 고민이 많이 필요한 문제입니다.

 

개인적으로는 프로그래머스 2단계 문제 중에 가장 어려웠던 문제라 생각이 듭니다.

 

그동안은 아무리 문제가 어려워도 검색을 해가면서까지 다른 풀이를 참고하지는 않았는데 이번 문제에서는 여러모로 검색의 도움을 많이 받았던 것 같습니다.

 

---

1. 어떤 방식으로 접근해야 할까 ?

 

우리의 목표는 쿼리 데이터를 인포 데이터에 매칭을 시켜서 점수대 이상의 사람들의 수를 찾는 것입니다.

 

데이터가 무수히 많을 경우를 생각해봅시다.

 

info로 주어지는 데이터 중 점수를 제외한 그 앞의 데이터 (java, backend, junior, pizza )의 경우는 선택지가 많지 않아 같은 조건으로 주어진 데이터를 동일한 key로 두고 value 값에는 점수만 들어가도록 객체 형태의 자료구조를 만들 수 있습니다.

 

저 같은 경우는 콘솔로 찍어 확인하기 편하도록 각 조건의 앞글자만 따고 key에 할당하였습니다.

 

우선 여기까지를 코드로 나타내면 아래와 같습니다.

const info_data = new Map();
info.forEach((v) => {
    v = v.split(" ");
    let key = `${v[0][0]}${
      v[1][0]
    }${v[2][0]}${v[3][0]}`;
    if (info_data.has(key)) {
      info_data.set(key, [...info_data.get(key), Number(v[4])]);
    } else {
      info_data.set(key, [Number(v[4])]);
    }

---

조건을 key 값으로 놔뒀기 때문에 우리는 query에서 만족하는 key값을 불러온 후 value에 있는 점수를 탐색하게 됩니다.

 

이때 이진 검색 알고리즘을 활용하면 검색시간을 많이 단축시킬 수 있습니다.

 

value 값으로 불러온 배열과 찾는 쿼리의 점수 값을 인자로 받아 이진 검색을 수행하는 함수를 외부 함수로 선언하였습니다.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

---

쿼리를 검색할 때 문자에 "-"가 있을 경우 조건을 고려하지 않겠다는 뜻입니다.

이 말은 즉슨 "----" 라는 조건이 주어지면 모든 경우의 수를 다 탐색하고 그게 맞는 key값을 다 대입시켜 value를 탐색해야 합니다.

저는 이러한 탐색을 위한 가능한 조건의 목록을 배열을 받아오기 위해 외부 함수로 두었습니다. 여기서 parameter는 조건의 앞글자만 딴 문자열입니다. (- 포함)

ex ) 'pfsc',  'c-sp' ,  '-bs-'

function condition(str) {
  let answer = [];
  const arr = [
    ["c", "j", "p"],
    ["b", "f"],
    ["j", "s"],
    ["c", "p"],
  ];
  function DFS(combine) {
    if (combine.length === 4) {
      answer.push(combine.join(""));
    } else {
      const i = combine.length;
      if (str[i] === "-") {
        for (let j = 0; j < arr[i].length; j++) {
          const combineCopy = combine.slice();
          combineCopy.push(arr[i][j]);
          DFS(combineCopy);
        }
      } else {
        const combineCopy = combine.slice();
        combineCopy.push(str[i]);
        DFS(combineCopy);
      }
    }
  }
  DFS([]);
  return answer;
}

 

---

다음은 Memoization의 활용입니다. 찾는 조건이 점수까지 같은 경우 우리는 두 번 탐색을 할 필요가 없이 Memoization을 관리하는 객체를 따로 두면 그것을 바로 불러와 값으로 사용할 수 있습니다. 여기서 key값은 조건+점수로 두었습니다.

if (query_data.has(key + v[7])) {
      answer.push(query_data.get(key + v[7])); // Memoization 불러오기
    } else {
      let count = 0;
      for (let x of condition(key)) {
        if (info_data.has(x)) {
          count +=
            info_data.get(x).length -
            binarySearch(info_data.get(x), Number(v[7]));
        }
      }
      answer.push(count);
      query_data.set(key + v[7], count); // Memoization 저장
    }

 

위의 내용을 다 합친 전체적인 코드는 아래와 같습니다.

function condition(str) {
  let answer = [];
  const arr = [
    ["c", "j", "p"],
    ["b", "f"],
    ["j", "s"],
    ["c", "p"],
  ];
  function DFS(combine) {
    if (combine.length === 4) {
      answer.push(combine.join(""));
    } else {
      const i = combine.length;
      if (str[i] === "-") {
        for (let j = 0; j < arr[i].length; j++) {
          const combineCopy = combine.slice();
          combineCopy.push(arr[i][j]);
          DFS(combineCopy);
        }
      } else {
        const combineCopy = combine.slice();
        combineCopy.push(str[i]);
        DFS(combineCopy);
      }
    }
  }
  DFS([]);
  return answer;
}

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}
function solution(info, query) {
  let answer = [];
  const info_data = new Map();
  const query_data = new Map();
  info.forEach((v) => {
    v = v.split(" ");
    let key = `${v[0][0]}${v[1][0]}${v[2][0]}${v[3][0]}`;
    if (info_data.has(key)) {
      info_data.set(key, [...info_data.get(key), Number(v[4])]);
    } else {
      info_data.set(key, [Number(v[4])]);
    }
  });
  for (let x of info_data.keys()) {
    info_data.get(x).sort((a, b) => a - b);
  }
  query.forEach((v) => {
    v = v.split(" ");
    let key = `${v[0][0]}${v[2][0]}${v[4][0]}${v[6][0]}`;
    if (query_data.has(key + v[7])) {
      answer.push(query_data.get(key + v[7])); // Memoization 불러오기
    } else {
      let count = 0;
      for (let x of condition(key)) {
        if (info_data.has(x)) {
          count +=
            info_data.get(x).length -
            binarySearch(info_data.get(x), Number(v[7]));
        }
      }
      answer.push(count);
      query_data.set(key + v[7], count);
    }
  });
  return answer;
}