프로개르머스 - 순위 검색 [ 효율성 실패 ]

function solution(info, query) {
  let book = {
    lan: "",
    pos: "",
    age: "",
    food: "",
    score: "",
  };
  let arr = [];
  for (let i = 0; i < query.length; i++) {
    let x = query[i].split(" and ");
    let y = x[3].split(" ");
    let point = 0;
    book.lan = x[0];
    book.pos = x[1];
    book.age = x[2];
    book.food = y[0];
    book.score = y[1];
    for (let i = 0; i < info.length; i++) {
      let x = info[i].split(" ");
      if (
        (book.lan === x[0] || book.lan === "-") &&
        (book.pos === x[1] || book.pos === "-") &&
        (book.age === x[2] || book.age === "-") &&
        (book.food === x[3] || book.food === "-") &&
        (Number(book.score) <= Number(x[4]) || book.score === "-")
      ) {
        point++;
      }
    }
    arr.push(point);
  }
  return arr;
}

내 코드는 상당히 간단하다.

book이라는 객체에 값들을 저장하고 이제 예시로 들어오는 값들을 모두 확인하는 것이다.

테스트 적인 면에서는 모두 합격을 하였지만 효율적인 면에서는 모두 실패를 하엿다 ㅠㅠ

그래서 잠시 쉬면서 어떻게 하면 효율적으로 코드를 짤수 있을까 고민을 해보았다.

• 결론적으로는 생각을 해내지 못했다 ㅠㅠ

function solution(info, query) {
  const answer = [];
  const infoMap = {};
  
  function combination(array, score, start) {
      const key = array.join("");
      const value = infoMap[key];
      
      if (value) {
          infoMap[key].push(score);
      } else {  
          infoMap[key] = [score];
      }
      
      for (let i = start; i < array.length; i++) {
          const temp = [...array];
          temp[i] = "-";
          combination(temp, score, i + 1);
      }
  }
  
  for (const e of info) {
      const splited = e.split(" ");
      const score = Number(splited.pop());
      combination(splited, score, 0);
  }
  
  for (const key in infoMap) {
      infoMap[key] = infoMap[key].sort((a, b) => a - b);
  }
  
  for (const e of query) {
      const splited = e.replace(/ and /g, " ").split(" ");
      const score = Number(splited.pop());
      const key = splited.join("");
      const array = infoMap[key];
      
      if (array) {
          let start = 0;
          let end = array.length;
          while (start < end) {
              const mid = Math.floor((start + end) / 2);
              
              if (array[mid] >= score) {
                  end = mid;
              } else if (array[mid] < score) {
                  start = mid + 1;
              }
          }
          
          const result = array.length - start;
          answer.push(result);
      } else {
          answer.push(0);
      }
  }
  
  return answer;
}

어.. 모르겠다... ㅋㅋㅋㅋㅋ

이분탐색 + 조합을 사용해서 문제를 해결 해야 한다고 하는데..

나는 아직까지는 도저히 모르겠다 ㅠㅠ 후에 내가 좀더 실력이 늘어난다면 그떄 다시 점검해 보도록 하자