순위 검색

오답 과정

오답 과정

이렇게 했더니 효율성에서 꽝이 나와씁니다...

1. hash로 다 저장을 한다! 이때 key의 이름을 그냥 다 붙인 걸로 만든다. 마치 다음처럼 말이다. infos = { javabackendjuniorpizza: [150] }

2. 그 다음에, score을 분리하고 query의 경우 정규표현식으로 해당되는 옵션들만 빼내준다. 마치 다음처럼 말이다. query = [backend, senior] score = 150

3. 결과적으로 쿼리를 모두 포함하는 키들을 찾아서, 점수에 맞는 애들을 필터해서 나온 배열 길이를 더해준다.

생략해도 됩니다! 틀렸으니까유 😂

const getInfos = (info) => {
  const infos = {};
  info.forEach(str => {
    const arr = str.split(" ");
    const score = parseInt(arr.pop());
    const key = arr.join("");
    if (infos[key]) infos[key].push(score)
    else infos[key] = [score];
  });
  return infos;
}
const solution = (info, query) => {
  let answer = [];
  const infos = getInfos(info);
  const infosKey = Object.keys(infos);

  const splitedQuery = query.map(q => q.split(/ and | |-/i));
  splitedQuery.forEach(query => {
    const score = query.pop();
    const filteredKey = infosKey.filter(key => query.every(v => key.includes(v)))

    const result = filteredKey.reduce((acc, key) => acc + infos[key].filter(cnt => cnt >= score).length, 0);
    answer.push(result)
  })
  return answer;
}

와우~ 대단하죠?! 👏👏

정답 과정

1. getInfos에서 다음과 같이 처리를 해줄 거에요.
• { javabackendjuniorpizza: [150] }
• 그럼 우리는, 이제 앞으로 hash를 통해 손쉽게 해당 쿼리에 해당하는 사람들의 점수를 갖고 올 수 있어요.

2. 분리하고, query 조건을 필터링해줄 거에요. 다음과 같이 말이죠.+
• - and backend and senior and - 150 → [ backend, senior, 150 ]
💡
왜 -까지도 없애죠?! 왜 -을 뺐냐면, 결국에는 특정 조건들만 key값에 들어가 있는지만 체크하면 되니까요!

3. 이제 이렇게 쿼리 친구들을 forEach로 돌려줍시다.
• 먼저 score을 분리해줘야겠죠? 분리해줍니다.
• 그러면 이제 필요한 쿼리들이 모두 존재하는 키를 찾아야 해요. 이는 getResult 함수에서 수행해줍시다.

4. getResult에서는 말이죠, 다음을 처리해줘요.
• 먼저 object 자료구조에서 키들을 다 뽑아내요. Object.keys(infos)
• 전체 키들을 뽑아낸 배열에 대해, 필터링을 해줍니다. 그럼 조건에 맞는 결과 값을 담은 배열이 반환되겠죠?
• 모든 조건이 맞을 때 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 클 수밖에 없습니다.
  return mid + 1; 
}

const getInfos = (info) => {
  const infos = {}; // 해시 테이블 생성해줄 거에요.
  info.forEach(str => { // 이제 해시 테이블에 `info`를 처리해줘야겠죠?!
    const arr = str.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;
}