[해쉬, 이진탐색, 문자열, regex, 정렬] 순위 검색 (카카오블라인드 2021)

https://school.programmers.co.kr/learn/courses/30/lessons/72412

 

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

• 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
• 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
• 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
• 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.

• 코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
• 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?

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

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

---

[문제]

지원자가 지원서에 입력한 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점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.

 

 

첫번째 풀이(정확성, 효용성 실패, 시간초과)

이중 for로 query와 info를 순회하면서 매 조건 마다 INFO배열에서 조건에 맞는 사람을 찾았다.

점수 오름차순으로 sort해서 내부 for에서 효율을 생각했지만

문자열을 처리하는데 코드가 복잡하고 무엇보다 시간을 초과했다.(그래도 나의 생각의 히스토리니까 기록)

 

function getMaxIndex(candidates, score) {
    let left = 0; 
    let right = candidates.length-1;
    while(left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (candidates[mid][4] < score) {
            left = mid+1;
        } else {
            right = mid-1;
        }
    }
    return left;
}

function solution(info, query) {
    var answer = [];
    const candidates = [];
    for (const i of info) {
        const [a, b,c,d, score] = i.split(' ');
        candidates.push([a, b, c, d, Number(score)]); // 점수문자열 숫자로 변환
    }
    candidates.sort((a, b) => a[4] - b[4]);
    
    const requirements = [];
    const regex = /\sand\s|\s/ // ' and ' 혹은 ' '에 따라split
    for (const q of query) {
        requirements.push(q.split(regex));
    }
    
    for (let i = 0; i < requirements.length; i++) {
        const [a, b, c, d, score] = requirements[i];
        const maxIndex = getMaxIndex(candidates, score);
        
        for (let j = maxIndex; j < candidates.length; j++) {
            let sum = 0;
            const [aa, bb, cc, dd, ee] = candidates[j];
            
            if (a === '-' || a === aa) sum++;
            if (b === '-' || b === bb) sum++;
            if (c === '-' || c === cc) sum++;
            if (d === '-' || d === dd) sum++;
            
            if (sum === 4) {
                answer[i] = (answer[i] || 0) + 1;
            }
        }
    }
    return answer;
}

 

왜 시간초과 했을까?

위에서 매 조건마다 INFO 배열에서 조건에 맞는 사람들을 찾았다 하지만 

info 배열의 크기는 1 이상 50,000 이하

query 배열의 크기는 1 이상 100,000 이하

이중 순회로 매번 지원자들을 찾는다면 효율성을 통과할 수 없다

 

• 지원자들을 가능한 그룹별로  미리 분류해두면 매 조건마다 지원자들을 INFO 배열에서 찾지 않아도 된다.
  • INFO배열을 먼저 순회해 가능한 경우를 모두 hash에 분류한다 { 경우: [점수] }
• 분류한 후 같은 경우의 지원자끼리 묶어두고, 해당 경우의 점수를 기준으로 오름차순 정렬한다
  • 이러면 "X이상 점수" 조건을 만족하는 사람 수를 구하기 편리하다.
  • 오름차순으로 정렬된 배열에서 X라는 숫자를 찾는 효율적인 방법으로 binary search를 사용할 수 있다. 이때, 배열에 X가 없을 수도 있으므로, 배열에서 X보다 크거나 같은 숫자가 처음 나타나는 위치를 찾아야 하며, 이는 lower bound를 이용한다
  • LOWER BOUND를 찾는 것은 특정 값 이상인 첫 번째 요소의 인덱스를 찾는 것을 의미합니다.
• 모든 경우 별 점수를 정렬한 뒤,  검색 조건마다  INFO 배열에서 지원자들을 찾지 않고, 미리 분류해둔 그룹에서 "경우" key로 점수배열을 찾고 그 중에서 X점 이상 맞은 지원자 수를 군한다.

 

두번째 풀이(정확성 통과, 효율성 시간초과)

각 경우를 만드는 법

조건이 있는지 없는지 2가지 경우와 (lanauge 혹은 '-')

4가지의 조건의 조합 (lanauge, position, career, food)

=>  2^4 = 16가지의 경우 (4중 for)

[🎈주의] query의 조건이 scoreObj 해쉬에 없는 경우는 조건을 만족하는 사람이 없으므로 패쓰!

 // scoreObj에 존재하지 않는 조건이면 만족하는 갯수는 0개
if (scoreObj[key] && scoreObj[key].length) {
  answer[i] = lowerBound(targetScore, scoreObj[key]);
}

// target점수 이상의 점수 갯수 반환
function lowerBound(target, scoreArr) {
  let min = 0;
  let max = scoreArr.length - 1;

  while (min <= max) {
    const mid = Math.floor((min + max) / 2);

    if (scoreArr[mid] < target) {
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }
  return scoreArr.length - min;
}

function solution(info, query) {
  var answer = new Array(query.length).fill(0);
  const scoreObj = {}; // {조건: 점수배열}

  // 각info로 만들 수 있는 모든 경우를 그룹별로 분류
  for (const i of info) {
    const [l, p, c, f, score] = i.split(" ");

    // language
    for (let aIndex = 0; aIndex < 2; aIndex++) {
      let language = "";
      if (aIndex === 0) language = l;
      else language = "-";

      // position
      for (let bIndex = 0; bIndex < 2; bIndex++) {
        let position = "";
        if (bIndex === 0) position = p;
        else position = "-";

        // career
        for (let cIndex = 0; cIndex < 2; cIndex++) {
          let career = "";
          if (cIndex === 0) career = c;
          else career = "-";

          // food
          for (let dIndex = 0; dIndex < 2; dIndex++) {
            let food = "";
            if (dIndex === 0) food = f;
            else food = "-";

            // scoreObj에 각 경우에 대한 점수추가
            const key = [language, position, career, food].join(" ");
            const numScore = parseInt(score);
            if (scoreObj[key]) {
              scoreObj[key].push(numScore);
              scoreObj[key].sort((a, b) => a - b); // 점수 오름차순 정렬
            } else {
              scoreObj[key] = [numScore];
            }
          }
        }
      }
    }
  }

  for (let i = 0; i < query.length; i++) {
    const regex = /\sand\s|\s/;
    const [l, p, c, f, targetScore] = query[i].split(regex);
    const key = [l, p, c, f].join(" ");

    // scoreObj에 존재하지 않는 조건이면 만족하는 갯수는 0개
    if (scoreObj[key] && scoreObj[key].length) {
      answer[i] = lowerBound(targetScore, scoreObj[key]);
    }
  }
  return answer;
}

 

✅ 최종풀이 (성공)

효율성 팁

위에선 각 경우마다 점수를 추가할때마다 sort를 해줬다.

=> hash를 모두 형성한 후에 한번에 sort 오름차순해준다.

  // hash를 다 만든후에 sort
  for (const [key, value] of Object.entries(scoreObj)) {
    scoreObj[key].sort((a, b) => a - b); // 점수 오름차순 정렬
  }

// target점수 이상의 점수 갯수 반환
function lowerBound(target, scoreArr) {
  let min = 0;
  let max = scoreArr.length - 1;

  while (min <= max) {
    const mid = Math.floor((min + max) / 2);

    if (scoreArr[mid] < target) {
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }
  return scoreArr.length - min;
}

function solution(info, query) {
  var answer = new Array(query.length).fill(0);
  const scoreObj = {}; // {조건: 점수배열}

  // 각info로 만들 수 있는 모든 경우를 hash로 만들어서 그룹별로 분류
  for (const i of info) {
    const [l, p, c, f, score] = i.split(" ");

    // language
    for (let aIndex = 0; aIndex < 2; aIndex++) {
      let language = "";
      if (aIndex === 0) language = l;
      else language = "-";

      // position
      for (let bIndex = 0; bIndex < 2; bIndex++) {
        let position = "";
        if (bIndex === 0) position = p;
        else position = "-";

        // career
        for (let cIndex = 0; cIndex < 2; cIndex++) {
          let career = "";
          if (cIndex === 0) career = c;
          else career = "-";

          // food
          for (let dIndex = 0; dIndex < 2; dIndex++) {
            let food = "";
            if (dIndex === 0) food = f;
            else food = "-";

            // scoreObj에 각 경우에 대한 점수추가
            const key = [language, position, career, food].join(" ");
            const numScore = parseInt(score);
            if (scoreObj[key]) {
              scoreObj[key].push(numScore);
            } else {
              scoreObj[key] = [numScore];
            }
          }
        }
      }
    }
  }

  // hash를 만든후에 sort
  for (const [key, value] of Object.entries(scoreObj)) {
    scoreObj[key].sort((a, b) => a - b); // 점수 오름차순 정렬
  }

  for (let i = 0; i < query.length; i++) {
    const regex = /\sand\s|\s/;
    const [l, p, c, f, targetScore] = query[i].split(regex);
    const key = [l, p, c, f].join(" ");

    // scoreObj에 존재하지 않는 조건이면 만족하는 갯수는 0개
    if (scoreObj[key] && scoreObj[key].length) {
      answer[i] = lowerBound(targetScore, scoreObj[key]);
    }
  }
  return answer;
}