[프로그래머스 lev2/JS] 순위 검색

문제 출처

프로그래머스 lev2 - 순위 검색

나의 풀이

1차시도 (정확성 통과, 효율성 실패)

정규표현식 /\sand\s|\s/ : (공백abc공백) 또는 (공백)
=> \s가 공백을 의미하고, /and/가 and 문자열을 의미한다.

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

  query.map(v => {
    const cpr = v.split(/\sand\s|\s/)
    const cprPoint = Number(cpr[cpr.length-1])
    let cnt = 0

    info.map(el => {
      const cur = el.split(' ')
      const curPoint = Number(cur[cur.length-1])
      let flag = true

      for(let i=0; i<cpr.length-1; i++){
        if(cpr[i] === '-') continue
        if(cpr[i] !== cur[i]) {
          flag = false
          break
        }
      }
      
      if(flag && cprPoint <= curPoint) cnt++

    })
    answer.push(cnt)
  })
  return answer
}

console.log(
  solution(
    [
      "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",
    ],
    [
      "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",
    ]
  )
); // [1, 1, 1, 1, 2, 4]

여전히 시간초과가 발생한다..

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

  for(let i=0; i<query.length; i++) query[i] = query[i].split(/\sand\s|\s/)
  for(let i=0; i<info.length; i++) info[i] = info[i].split(' ')

  for(let i=0; i<query.length; i++){
    let cnt = 0

    for(let j=0; j<info.length; j++){
      if(query[i][0] !== "-" && query[i][0] !== info[j][0]) continue
      if(query[i][1] !== "-" && query[i][1] !== info[j][1]) continue
      if(query[i][2] !== "-" && query[i][2] !== info[j][2]) continue
      if(query[i][3] !== "-" && query[i][3] !== info[j][3]) continue

      if(Number(query[i][4]) <= Number(info[j][4])) cnt++
      // if (
      //   ((query[i][0] !== "-" && query[i][0] === info[j][0]) || query[i][0] === "-") &&
      //   ((query[i][1] !== "-" && query[i][1] === info[j][1]) || query[i][1] === "-") &&
      //   ((query[i][2] !== "-" && query[i][2] === info[j][2]) || query[i][2] === "-") &&
      //   ((query[i][3] !== "-" && query[i][3] === info[j][3]) || query[i][3] === "-") &&
      //   Number(query[i][4]) <= Number(info[j][4])
      // ) cnt++
    }   
    answer.push(cnt)
  }
  return answer
}

다른 풀이

해시와 이진탐색을 사용해야 효율성을 통과할 수 있는 문제였다..

[1]
info 배열들을 문자열로 만들어서 key로 할당한다.
value에는 배열 형태로 점수들을 할당한다.
미리 가능한 문자열 조합을 미리 구해서 해시로 저장해놓는다.

{
  javabackendjuniorpizza: [ '150' ],
  '-backendjuniorpizza': [ '150' ],
  '--juniorpizza': [ '150' ],
  '---pizza': [ '150', '260' ],
  '----': [ '150', '210', '150', '260', '80', '50' ],
  '--junior-': [ '150', '80' ],
  '-backend-pizza': [ '150', '260' ],
  '-backend--': [ '150', '260', '80', '50' ],
  '-backendjunior-': [ '150', '80' ],
  'java-juniorpizza': [ '150' ],
  'java--pizza': [ '150' ],
  'java---': [ '150', '80' ],
  'java-junior-': [ '150', '80' ],
  ...
}

[2]
이분탐색을 하기 위해서는 값이 정렬되어 있어야 하므로,
for ...in을 사용해서 객체의 value를 정렬한다.

[3]
start와 end 값을 할당해서 이분탐색을 진행한다.
이분탐색은 계속해서 범위를 1/2로 줄여가므로 이분탐색의 시간복잡도는 O(logN)이다. 모든 요소를 탐색하는 것(O(N))보다 훨씬 빠르다.

const solution = (info, query) => {
  let answer = [];
  let map = {};
  
  const combination = (infos, score, map, start) => {
    let key = infos.join("");  // infos 배열을 문자열로 합쳐서 key로 사용한다. 
    let value = map[key];      // 객체로 key를 관리할 것이므로, 값이 있는지 없는지 확인하기 위해서

    if(value){ // 값이 있으면 push
      map[key].push(score);
    }else{ // 값이 없으면 배열 형태로 만들어서 값 생성하기. (key는 infos 문자열, value는 점수)
      map[key] = [score];
    }

    // -를 이용해 조합 만들기
    for(let i=start; i<infos.length; i++){
      let combiArr = [...infos];
      combiArr[i] = '-';
      
      combination(combiArr, score, map, i+1);
    }
  }
  
  // 이분탐색
  function binarySearch(map2, key2, score2){
    let scoreArr = map2[key2];
    
    if(scoreArr){
      var start = 0;
      var end = scoreArr.length;
      
      while(start < end){
        var mid = Math.floor((start+end)/2);
        
        if(scoreArr[mid] >= score2){ // 현재 가리키는 값보다 내가 찾는 값이
            end = mid;
        }else if(scoreArr[mid] < score2){
            start = mid + 1;
        }
      }
      
      return scoreArr.length - start;
    }
    else return 0
  }
  
  // 1. -로 가능한 모든 조합을 미리 만들어 놓기
  for(let i=0; i<info.length; i++){
    let infos = info[i].split(" ");
    let score = infos.pop();
    
    combination(infos, score, map, 0);
  }
  
  // 2. 이분탐색을 진행하기 위해 미리 정렬
  for(let key in map){
    map[key].sort((o1, o2) => o1 - o2);
  }

  // 3. 이분탐색 진행
  for(let i=0; i<query.length; i++){
    let querys = query[i].replace(/ and /g, "").split(" "); // 질문항목과 점수로 구분하기
    let score = Number(querys.pop());
  
    answer.push(binarySearch(map, querys.join(""), score));
  }
  return answer;
}

참고

[프로그래머스] 순위 검색 javascript