[JS] 순위 검색

프로그래머스 순위 검색

• 난이도 LV.2

문제 풀이

처음에는 그냥 비교 탐색으로 했다.

조건에 맞는 count 면 ++ 하여서 해당 조건에 만족하는 것을 push 시켜주었다.

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

    for(let q of query){
        let [lan,par,car,last]=q.split("and").map(item=>item.trim())
        let [foo,sco]=last.split(" ");
        let count=0;

        for(let i of info){
            let [a,b,c,d,e]=i.split(" ");


            if(lan==="-" || lan===a){
                if(par==="-" || par===b){
                    if(car==="-" || car===c){
                        if(foo==="-" || foo===d){
                            if(+sco <= + e){
                                count++;
                            }
                        }
                    }
                }
            }
        }
        answer.push(count);

    }
    return answer;
}

그렇게 했을 때, 정확성은 다 맞는데 효율성에서 시간 초과가 발생한다.

다시 문제로 돌아가보면, 비교 탐색을 했을 때 50,000 * 100,000 이므로 최악의 경우 50억번을 반복해야한다.

그래서 비교 탐색을 하지 않고, 탐색하는 방법을 이진 탐색으로 하기로 했다.

- 이진 탐색 적용 풀이

처음에 이진 탐색을 어떻게 적용해야하는지 고민했다.

1. 모든 경우의 수를 넣어준다.

만약 info 가 "java backend junior pizza 150" 이라고 할 때, query에서 해당하는 조건은

• java backend junior pizza
• - backend junior pizza
• java - junior pizza
• java backend - pizza
• java backend junior -
• - - junior pizza
• - backend - pizza
• - backend junior -
• java - - pizza
• java - junior -
• java backend junior - -
• java - - -
• - backend - -
• - - junior -
• - - - pizza
• - - - - 

위에 16개의 경우의 수에 가능할 것이다. 파이썬은 Combination 함수가 내장되어있는데 자바스크립트는 그렇지 않아서 불편하다 😅

16개 정도는 손으로 쓸 수 있으니 그냥 노가다로 작업했다. (만약 그 이상의 조합을 구해야한다면 함수로 짜야할 것 같다 !) 

const getComb=(item)=>{
    const [a,b,c,d,e]=item.split(" ");

    const comb=[
        `${a}${b}${c}${d}`,
        `-${b}${c}${d}`,
        `${a}-${c}${d}`,
        `${a}${b}-${d}`,
        `${a}${b}${c}-`,
        `--${c}${d}`,
        `-${b}-${d}`,
        `-${b}${c}-`,
        `${a}--${d}`,
        `${a}-${c}-`,
        `${a}${b}--`,
        `${a}---`,
        `-${b}--`,
        `--${c}-`,
        `---${d}`,
        `----`,   
    ]

    return {
        arr:comb,
        score: +e
    }
}

 

이렇게 구한 조합을 Map에 넣어준다.

    const comb=new Map();
    
    for(let i of info){
        const {arr,score}=getComb(i);
        
        for(let str of arr){
            const target=comb.get(str);
            comb.set(str, target ? [...target,score] : [score]);
        }
    }

 

이렇게 했을 때, query 문에서 index로 찾으면 되기 때문에 O(1)의 시간이 걸린다.

그런데 comb.set을 해줄 때, spread 문법을 사용해줬는데 그랬을 때 효율성에서 점수가 까였다.

    for(let i of info){
        const {arr,score}=getComb(i);
        
        for(let str of arr){
            const target=comb.get(str);
            let cur;
            
            if(!target) cur=[score];
            else{
                cur=target;
                cur.push(score)
            }
            comb.set(str, cur);
        }
    }

그래서 더 복잡한 if/else 문으로 분리해주었다

 

 

3. score 정렬해주기

이분 탐색은 정렬이 되어있다는 조건이 중요하므로 정렬을 해주어야 한다.

    for(let [key, value] of comb){
        const result=value.sort((a,b)=>a-b);
        comb.set(key, result);
    }

 

4. 현재 score보다 큰 경우 찾기

 for(let q of query){
        let [a,b,c,last]=q.split("and").map(item=>item.trim());
        let [d,score]=last.split(' ');
        score = + score
    }

먼저, query 같은 경우에는 ' java and backend and junior and pizza 100 ' 과 같이 and로 분리되다가 마지막에 score가 나오기 때문에 다음과 같이 처리해주었다.

 

    
        const target=`${a}${b}${c}${d}`
        const arr=comb.get(target);
        
        
        let left=0;
        let right=arr.length;
        
        while(left<right){
           let mid=Math.floor((left+right)/2);
            
            if(arr[mid] < score) left=mid+1;
            else right=mid;
        }

map 에 저장되어 있는 경우의 수를 꺼내주고, 이분 탐색을 해준다.

 

• mid 값이 score 보다 작은 경우에는, left를 높혀서 더 높은 점수대가 search 될 수 있도록 해준다.
• mid 값이 score보다 크거나 같은 경우에는, right 값을 낮춰줘서 더 낮은 점수대가 search 될 수 있도록 해준다.

 

그리고, 내가 찾고 싶은 수는 score에 만족하는 최고로 낮은 idx이기 때문에 

        answer.push(arr.length-left);

전체 length 에서 left 값을 빼준다.

 

 

5. 런타임 해결

 

이렇게 했을 때, 런타임이 발생하는데 그 이유는 map에서 가져올 때 해당 경우의 수가 없을 수 있기 때문이다.

        const arr=comb.get(target);
        
        if(!arr) {
            answer.push(0);
            continue;
        }

 

그래서 다음과 같은 코드를 추가하여, arr가 있는지 없는지 판단해주었다.

 

전체코드

const getComb = (item) => {
  const [a, b, c, d, e] = item.split(" ");

  const comb = [
    `${a}${b}${c}${d}`,
    `-${b}${c}${d}`,
    `${a}-${c}${d}`,
    `${a}${b}-${d}`,
    `${a}${b}${c}-`,
    `--${c}${d}`,
    `-${b}-${d}`,
    `-${b}${c}-`,
    `${a}--${d}`,
    `${a}-${c}-`,
    `${a}${b}--`,
    `${a}---`,
    `-${b}--`,
    `--${c}-`,
    `---${d}`,
    `----`,
  ];

  return {
    arr: comb,
    score: +e,
  };
};
function solution(info, query) {
  var answer = [];
  let comb = new Map();

  for (let i of info) {
    const { arr, score } = getComb(i);

    for (let str of arr) {
      const target = comb.get(str);
      let cur;

      if (!target) cur = [score];
      else {
        cur = target;
        cur.push(score);
      }
      comb.set(str, cur);
    }
  }

  for (let [key, value] of comb) {
    const result = value.sort((a, b) => a - b);
    comb.set(key, result);
  }

  for (let q of query) {
    let [a, b, c, last] = q.split("and").map((item) => item.trim());
    let [d, score] = last.split(" ");

    score = +score;

    const target = `${a}${b}${c}${d}`;
    const arr = comb.get(target);

    if (!arr) {
      answer.push(0);
      continue;
    }

    let left = 0;
    let right = arr.length;

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

      if (arr[mid] < score) left = mid + 1;
      else right = mid;
    }

    answer.push(arr.length - left);
    // console.log(arr,score,mid, left,right)
  }

  return answer;
}