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

function solution(info, query) {
  for (let i = 0; i < info.length; i++) {
    info[i] = info[i].split(" ");
  }
  console.log(info);
  for (let i = 0; i < query.length; i++) {
    query[i] = query[i].split(" ");
    query[i] = query[i].filter((el) => {
      return el !== "and";
    });
  }
  console.log(query);
  let result = [];
  for (let i = 0; i < query.length; i++) {
    let filterStart = info;
    for (let j = 0; j < query[i].length; j++) {
      if (query[i][j] !== "-") {
        filterStart = filterStart.filter((el) => {
          if (j === 4) {
            if (Number(el[j]) >= query[i][j]) return el;
          } else if (el[j] === query[i][j]) return el;
        });
        if (filterStart.length === 0) {
          j = query[i].length;
        }
      }
    }
    result.push(filterStart.length);
  }
  return result
}

처리조건

즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.

* [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?

풀이

[     "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",   ]

Info에 해당하는 지원자 정보 와 query에 해당하는 검색 조건

 

우선 info와 query를 이중 배열형태로 만들기 위해 for문을 돌린다. query 같은 경우 위 음식종류 다음에 쉼표 구분없이 바로 점수가 붙여지므로 주의해서 배열을 만든다

 

만든 배열을 filterStart에 6개의 검색조건마다 한번씩 실행되면서 지원자인 info 배열을 검색하게 되는데 "-"인경우 무시하고 다음 index를 검사하고 아닌경우 해당하는 인덱스끼리 filter하여 맞으면 자기자신에게 다시 할당한다. 마지막 j가 4로 점수 계산을 할 때 Number로 타입을 바꾸어 검색 점수보다 큰 지 확인하여 최종적으로 필터된 filterStart가 남게되고 length를 result에 6개의 검색조건이 하나씩 돌 때마다 push하여 마지막에 result를 리턴한다.

 

 

문제가 발생했다. 이진탐색을 사용하지 않아서 처리속도가 너무 느리다. 음식까지 검색이 완료 되면 해당하는 배열값의 마지막인자인 점수는 하나로 모아 이진탐색으로 검색해야할 것 같다.

 

  const binarySearch = (arr, target) => {
    let left = 0;
    let right = arr.length - 1;
    let mid = Math.floor((left + right) / 2);
    while (left <= right) {

      if (arr[mid] === target) return mid;
      if (arr[mid] < target) left = mid + 1;
      else right = mid - 1;

      mid = Math.floor((left + right) / 2);
    }
    // 기준이 되는 인덱스는, 여기서 나온 값보다 항상 1이 더 큽니다. 따라서 +1을 해주죠!
    return mid + 1;
  };

arr로 [10,20,30,40] 의 넘버타입 요소가 들어가 sort 오름차순 정리된 배열이 들어가고

target으로 20인 string이 들어 갈 시 20보다 작은 요소가 몇개인지 검색하여 내놓는다.