시작하며 🌈

최근에 밀린 약속하랴, 따로 공부하랴, 완벽한 글은 제대로 쓰지도 못하고
사실상 임시 글만 5개 만들었네유...😂😂 그래도 조만간 포스팅해야겠어유!!

일단 오늘은 간만에 스터디할 겸, 알고리즘 문제를 풀었어오! 해시 문제였는데요!

💬 거의... 1주일만에 푼 것 같군요... 호오...

저한테는 꽤나 효율성 측면에서 어려워서, 머리를 쥐어짜내다 결국 풀었던 문제에요! 이상하게 레벨 2 문제라는데, 체감은 레벨 3에서 어려운 축이었던 것 같아요. 그래도 일단 최대한 함수형으로 풀려고 노력했어요.

• 결국 저같은 꿈나무들에게는 많이 헷갈려할 것 같은 문제라, 이에 대해 도움이 되고자,
• 그리고 저 역시 다음에는 헤매지 않고자 글로 남깁니다!

풀이 과정

1. getInfos에서 다음과 같이 처리를 해줄 거에요.**
   • { javabackendjuniorpizza: [150] }
   • 그럼 우리는, 이제 앞으로 hash를 통해 손쉽게 해당 쿼리에 해당하는 사람들의 점수를 갖고 올 수 있어요.
2. 분리하고, query 조건을 필터링해줄 거에요. 다음과 같이 말이죠.
   - and backend and senior and - 150 → [ backend, senior, 150 ]

   왜 -까지도 없애죠?!
   왜 -을 없앴냐면, 결국에는 특정 조건들만 key값에 들어가 있는지만 체크하면 되니까요!

3. 이제 이렇게 쿼리 친구들을 forEach로 돌려줍시다.
   • 먼저 score을 분리해줘야겠죠? 분리해줍니다.
   • 그러면 이제 필요한 쿼리들이 모두 존재하는 키를 찾아야 해요.
     이는 **getResult 함수에서 수행해줍시다.**
4. getResult에서는 말이죠, 다음을 처리해줘요.
   • 먼저 object 자료구조에서 키들을 다 뽑아내요.
   • 전체 키들을 뽑아낸 배열에 대해, 필터링을 해줍니다.
     그럼 조건에 맞는 결과 값을 담은 배열이 반환되겠죠?
   • 모든 조건이 맞을 때 true를 뱉는 Array.every내장 메서드를 써줍시다.
     그러면 모든 조건을 만족하는 키만 나와요.
   • 이를 reduce를 통해 모두 더해주는 거에요.
   • 쭉 더해줄 때마다 key 쪽에서 정렬된 점수 배열이 나올 거에요.
     이분 탐색을 해주어, infos[key]의 길이 - infos[key] 배열 중 score 의 위치 인덱스 값을 하면, 결국 해당 쿼리의 조건을 만족하며, 점수가 같거나 더 높은 애들만 나오겠죠?
   • 결국 숫자 타입의 결과 값을 반환하는 겁니다.
5. 반환된 getResult의 값을 이제 answer에 push 해줍니다.

// 이분 탐색입니다. 해당 값이 어느 인덱스에 있을지를 탐색하여 결과를 반환합니다.
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; 
}

const getInfos = (info) => {
  const infos = {}; // object를 생성해줄 거에요.
  info.forEach(infoString => { // 이제 object에 `info`를 처리해줘야겠죠?!
    const arr = infoString.split(" "); // 먼저 " " 기준으로 string을 분리해줍시다.
    const score = parseInt(arr.pop()); // 정수로 바꿔줄 거에요.
    const key = arr.join(""); // key를 javabackendjuniorpizza와 같은 형태로 해줄 거에요.
    if (infos[key]) infos[key].push(score)
    else infos[key] = [score]; // [150]의 형태로 배열에 점수를 넣어줘요.
  });
  for (const key in infos) {
    // 다 처리된 이후에는 각 키의 점수 배열을 정렬해줍니다.
    // 이건 이분탐색을 위한 거에요.
    infos[key].sort((a, b) => a - b); 
  }
  return infos;
}

const getResult = (infos, query, score) => {
  // 키들을 배열 형태로 갖고 옵시다.
  const infosKey = Object.keys(infos);
  // 여기서 이제 키들에 대해 쿼리 조건을 만족하는 것들을 필터링해서 배열로 반환하고 (filter)
  // reduce로 전체 점수 배열의 길이값 - 이분 탐색 결과 인덱스 값을 해줍니다.
  // 그러면 결국 값이 같거나 큰 애들의 수만큼 값이 나오겠죠? (정렬되어 있으니까요)
  // 이를 누산해줍니다.
  return infosKey
    .filter(key => query.every(v => key.includes(v)))
    .reduce((acc, key) => acc + infos[key].length - binarySearch(infos[key], score), 0);
}

const solution = (info, query) => {
  let answer = [];
  const infos = getInfos(info); // solution
  query
    .map(q => q
       .split(/ and | |-/i) //' and '와 ' '와 '-'이 들어가 있는 친구들 기준으로 split 처리해줘요.
       .filter(v => v !== "") // `split`에 의해 값이 "" 처리가 된 친구들을 없애줍니다.
    ) // 쿼리 조건들을 필터링해줄 거에요.
    .forEach(query => {
      const score = query.pop();
      const result = getResult(infos, query, score);
      answer.push(result) // getResult로 인해 누산된 결과값을, answer에 넣어줍시다.
    })
  return answer;
}

결과 💻

결과적으로 어설픈 함수형으로 짰지만, 제한시간 안에 풀 수 있었어요! 😆

마치며 👏

문제가 꽤나 어려워서 생각하느라 골치 아팠지만, 결국 풀어서 기분이 좋아요!
(++ 이게 레벨 2인가... 하면서 현타도 엄청 많이 들었네유😂)

한편으로는 부족한 만큼 성장하는 재미로 코딩하니, 여튼 제 힘으로 풀어서 기분이 너무 좋아요!
다들 즐겁게 코딩하길 바라며, 이상 🌈