[프로그래머스] 2021 KAKAO BLIND RECRUITMENT -> 순위 검색 - 자바스크립트

[문제]

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

• info 배열의 크기는 1 이상 50,000 이하입니다.
• info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
  • 개발언어는 cpp, java, python 중 하나입니다.
  • 직군은 backend, frontend 중 하나입니다.
  • 경력은 junior, senior 중 하나입니다.
  • 소울푸드는 chicken, pizza 중 하나입니다.
  • 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
• query 배열의 크기는 1 이상 100,000 이하입니다.
• query의 각 문자열은 "[조건] X" 형식입니다.
  • [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
  • 언어는 cpp, java, python, - 중 하나입니다.
  • 직군은 backend, frontend, - 중 하나입니다.
  • 경력은 junior, senior, - 중 하나입니다.
  • 소울푸드는 chicken, pizza, - 중 하나입니다.
  • '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
  • X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
  • 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
  • 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

---

<아이디어>

프로그래머스 레벨2임에도 효율성덕분에 아주 괴랄한 문제였다. 

[1번째] 맨 처음 문제를 봤을때는 일단 정확성부터 생각하고 코드를 짰다.

function solution_2(info, query) {
  var answer = [];
  let user = [];

  for (let i = 0; i < info.length; i++) {
    user.push(info[i].split(" "));
  }
  for (let i = 0; i < query.length; i++) {
    let match = 0;
    let condition = query[i].split(" ");
    for (let j = 0; j < user.length; j++) {
      let targetUser = user[j];
      if (
        (condition[0] == "-" || targetUser[0][0] == condition[0][0]) &&
        (condition[2] == "-" || targetUser[1][0] == condition[2][0]) &&
        (condition[4] == "-" || targetUser[2][0] == condition[4][0]) &&
        (condition[6] == "-" || targetUser[3][0] == condition[6][0]) &&
        (condition[7] == "-" || Number(targetUser[4]) >= Number(condition[7]))
      ) {
        match++;
      }
    }
    answer.push(match);
  }
  return answer;
}

그 결과 정확성은 좋았지만 효율성에서 다 터졌다. 가능한 최적화를 다 했다. 문자열비교에서 여러개 비교에서 하나만 하도록, if문 안에서 빠르게 true가 되도록 조건 위치도 바꿨는데 안됐다. 결국엔 로직 초반부터 잘못된 것을 알게되었다.

 

[2번째] 그리고 새로운 아이디어를 생각하다. Map를 이용한 구현을 해보기로 했다.

해서 user 정보를 가져다가 쪼개고 값의 첫번째 문자를 뽑아서 key를 만들었다.

예를 들어 

첫 조건 : cpp, java, python => c , j, p 이런식으로 만들고 맨 마지막 점수만 배열로 만들어서 넣었다.

  for (let i = 0; i < info.length; i++) {
    let user = info[i].split(" ");
    let userkey = `${user[0][0]}${user[1][0]}${user[2][0].toUpperCase()}${user[3][0].toUpperCase()}`;
    if (userMap.has(userkey)) {
      userMap.set(userkey, [...userMap.get(userkey), Number(user[4])]);
    } else {
      userMap.set(userkey, [Number(user[4])]);
    }
  }

여기서 뜬금없이 toUpperCase()가 3,4번 문자에 있는 이유는 => 후에 해당 조건을 고려하지 않는 - 를 처리하기 위함이다.

따라서 로직을 돌다 user 정보로 key를 만들고 key가 있으면 해당 배열을 가져와서 하나를 추가해서 넣어주고,

없으면 만드는 식으로 진행하였다.

그 결과, Map에서 볼수 있듯이 jbJP : java, backend, junior, pizza, 그리고 점수 150이 들어갔다.

이렇게 함으로써 각각의 조건에 따른 key와 점수로 이뤄진 배열을 가진 value의 userMap를 만들었다.

그런 다음 user 정보가 파악이 되었으면 점수를 오름차순으로 정렬을 해주었다.

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

맨 처음 코드에는 정렬로직 없이 각각의 userMap에서 filter로 큰걸 찾고 길이를 구하는 방식이었는데, 여기서 효율성이 다 터져나갔다.

그래서 이진탐색을 쓰기 위해서 한번 정렬을 해주었다.(알다시피 이진탐색은 정렬된 값에서만 사용가능하다)

  for (let i = 0; i < query.length; i++) {
    let count = 0;
    let condition = query[i].split(" ");
    let conditionKey = `${condition[0][0]}${condition[2][0]}${condition[4][0].toUpperCase()}${condition[6][0].toUpperCase()}`;
    for (let [key, value] of userMap) {
      conditionKey = conditionKey.replace(/\-/g, "");
      let contain = true;
      for (let i = 0; i < conditionKey.length; i++) {
        if (!key.includes(conditionKey[i])) {
          contain = false;
          break;
        }
      }
      if (contain) {
        const index = binarySearch(value, Number(condition[7]));
        count += value.length - index;
      }
    }
    answer.push(count);
  }

그 다음에 조건인 query를 하나씩 돌면서 query를 key로 만들어주는 작업을 또 했다. 이걸 통해서 userMap를 조회해야하기 때문이었다.

근데 이때 query에는 "-"가 있다.  아래와 같이 설명이 되어있다.

'-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.

하지만 내가 만들 key에선 다 없애버렸다. 없앨수 있는 이유는 중복이 없기 때문이다.

언어는 c,j,p 직군은 b,f 경력은 J,S, 소울푸드는 C,P 로 mapping해 놨다. 

그리고 로직을 돌면서 userMap의 key가 query의 key를 포함하고 있는지 확인했다.

만약 userMap의 key  : jbJP 는 query의 key : j-JP에 속한다고 볼수 있다.

따라서 j-JP => jJP => jbJP와 하나씩 비교해서 querykey의 각 문자를 userMap의 key가 다 들고 있으면 해당 key로 userMap의 value를 가져와서 이제 마지막 조건인 점수로 비교하면 되는 것이다.

최적화가 들어간 부분이 점수비교 부분이었는데,  userMap의 사이즈는 최대 3*2*2*2다. 하지만 value의 배열크기는 들어온 수만큼 그대로 증가한다. 따라서 앞에서 정렬을 하고 여기서 이진탐색을 통해 원하는 값보다 큰 시작 index를 찾는다.

그리고 해당 value.length - index를 한 값이 원하는 조건에 맞는 user 수가 된다.

<내 코드>

function solution(info, query) {
  let answer = [];
  let userMap = new Map();

  for (let i = 0; i < info.length; i++) {
    let user = info[i].split(" ");
    let userkey = `${user[0][0]}${user[1][0]}${user[2][0].toUpperCase()}${user[3][0].toUpperCase()}`;
    if (userMap.has(userkey)) {
      userMap.set(userkey, [...userMap.get(userkey), Number(user[4])]);
    } else {
      userMap.set(userkey, [Number(user[4])]);
    }
  }
  for (let [key, value] of userMap) {
    userMap.set(
      key,
      value.sort((a, b) => a - b)
    );
  }
  for (let i = 0; i < query.length; i++) {
    let count = 0;
    let condition = query[i].split(" ");
    let conditionKey = `${condition[0][0]}${condition[2][0]}${condition[4][0].toUpperCase()}${condition[6][0].toUpperCase()}`;
    for (let [key, value] of userMap) {
      conditionKey = conditionKey.replace(/\-/g, "");
      let contain = true;
      for (let i = 0; i < conditionKey.length; i++) {
        if (!key.includes(conditionKey[i])) {
          contain = false;
          break;
        }
      }
      if (contain) {
        const index = binarySearch(value, Number(condition[7]));
        count += value.length - index;
      }
    }
    answer.push(count);
  }
  return answer;
}
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

---

코드는 아래에 올려두었다.

gyeongseokKang/coding_test