[알고리즘 연습] 프로그래머스 순위 검색 (LEVEL 2, 자바스크립트)

문제

프로그래머스

---

풀이

• 문자열 조작, 재귀, 이분 탐색을 모두 구현해서 풀어야 하는 문제로 단계적으로 차근차근 구현하면 어렵지 않게 풀 수 있는 문제였다.
• 재귀를 통해 조건의 각 자리에 한번은 조건 자체를 한번은 '-' 를 대입하여 모든 경우의 수를 구해준다. (시간 초과가 발생하지 않는다.)
• 이때 각 조건에 대한 점수는 배열 형태로 저장하고 오름차순으로 정렬한다.
• query 배열을 순회하며 조건에 해당하는 점수 배열에서 이분 탐색을 수행하여 점수의 하한선을 구한다.
  • query 배열에 있는 조건이 아까 구한 경우의 수에 없을 수 있다.

소스 코드

function solution(info, query) {
    const answer = [];
    const map = {};
    
    const dfs = (arr, str, idx, score) => {
      if (idx === 4) {
        if (map[str]) map[str].push(score);
        else map[str] = [score];
        
        return;
      }
        
      dfs(arr, str + arr[idx], idx + 1, score);
      dfs(arr, str + '-', idx + 1, score);
    }
    
    const binary_search = (arr, target, low, high) => {
      while (low < high) {
        let mid = Math.floor((low + high) / 2);
          
        if (arr[mid] >= target) high = mid;
        else low = mid + 1;
      }
        
      return low;
    }
    
    for (const item of info) {
      const arr = item.split(' ');
      const score = arr.pop();
      
      dfs(arr, '', 0, +score);
    }
    
    for (const key of Object.keys(map)) map[key].sort((a, b) => a - b);
    
    for (const q of query) {
      const temp = q.split(' ');
      const score = temp.pop();
      const str = temp.filter((el) => el !== 'and').join('');
      
      if (map[str]) {
        const len = map[str].length
        const low = binary_search(map[str], +score, 0, len);
        answer.push(len - low)
      } else {
        answer.push(0)
      }
    }
    
    return answer;
}