Level 2️⃣ - 순위 검색(2021 KAKAO BLIND RECRUITMENT)

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

프로그래머스

문제 접근

핵심 요구사항

각 query 조건에 맞는 인원이 몇 명인지 반환한다.

설계

1. Info를 통해 지원자 정보 테이블을 이차원 배열로 구현한다.

2. query를 순회하면서, 각 query 조건에 맞는 사람을 카운팅한다.

 

문자열 관련 문제라고 생각하고 O(n^2)으로 접근했다. 정확성은 모두 통과를 했지만 효율성이 0이 나왔다.

 

query의 최대값이 10만이고 Info의 최대값이 5만인데 query를 순회할 때마다 지원자 테이블을 순회하기 때문에 10만*5만의 경우가 발생하므로 시간초과가 발생하는 것 같다. 이 로직 자체를 수정해야한다는 생각이 들었다.

이런 경우에 해시맵을 사용하면 해결되는 경우가 있었다. 하지만 지금 문제에서는 어떤 데이터를 해시맵으로 다뤄야되는지 감이 오지 않는다...

function solution(info, query) {
    const ret = [];
    const userTable = [];
    info.forEach((elem)=>{
        userTable.push(elem.split(" "));
    });
    
    query.forEach((elem)=>{
        let cnt = 0;
        let tmp = [];
        let a = elem.split("and");
        a.forEach((c, idx)=>{
           if(idx === 3){
               let b = c.split(" ");
               b.forEach((t)=> tmp.push(t));
           }
           else tmp.push(c); 
        });
        tmp = tmp.filter((elem) => elem).map((elem) => elem.trim());
        for(let i = 0; i<userTable.length; i++){
            let flag = 1;
            for(let j = 0; j<userTable.length; j++){
                if(tmp[j] === '-') continue;
                if(j !== 4 && tmp[j] !== userTable[i][j] || j === 4 && Number(tmp[j]) > Number(userTable[i][j])){
                    flag = 0;
                    break;
                }
            }
            if(flag) cnt++;
        }
        ret.push(cnt);
    });
    return ret;
}

 

설계 수정

1. 객체 활용하기 (or 해시맵)

https://velog.io/@young_pallete/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%9C%EC%9C%84-%EA%B2%80%EC%83%89JavaScript

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

해당 블로그에서 Info를 활용해 Object를 사용하는 아이디어를 활용해보고자 했다.

언어, 직군, 경력, 소울 푸드에 해당하는 문자열을 key로 지정하고 점수를 value형태의 데이터로 저장한다.

"javabackendjuniorpizza" : [150] 이런 형태가 된다.

 

하지만 효율성이 0이 나왔다. 입력 조건을 살펴보니 조건을 만족하는 사람들 중, 코테 점수를 X점 이상 받은 사람을 체크할 때 시간초과가 나올 수 있음을 알았다.

function getInfos(info){
    const infos = {};
    info.forEach(infoString => {
        const arr = infoString.split(" ");
        const score = Number(arr.pop());
        const key = arr.join("");
        if(infos[key]) infos[key].push(score);
        else infos[key] = [score];
    });
    return infos;
}

function getResult(infos, query, score){
    let cnt = 0;
    const infosKey = Object.keys(infos);
    const a = infosKey.filter(key => query.every(v => key.includes(v)));
    // ❌최악의 경우 5만*5만이 나오기 때문에 시간 초과가 나올 수 있다.
    a.forEach((key)=>{
        infos[key].forEach((elem)=>{
            if(score <= elem) cnt++;
        });
    });
    return cnt;
}

function solution(info, query) {
    let answer = [];
    const infos = getInfos(info);
    query.forEach((elem)=>{
        let tmp = [];
        let a = elem.split("and");
        a.forEach((c, idx)=>{
            if(idx === 3){
                let b = c.split(" ");
                b.forEach((t) => tmp.push(t));
            }
            else tmp.push(c);
        });
        tmp = tmp.map((elem) => elem.trim()).filter((elem) => elem && elem !== "-");
        const score = tmp.pop();
        const result = getResult(infos, tmp, score);
        answer.push(result);
    });
    return answer;
}

 

2. 이진탐색 활용하기

그렇다면 조건을 만족하는 사람들 중, 코테 점수가 X점 이상인 사람을 찾으려면 이진탐색을 활용해야한다.

target은 target 이상인 사람들이 몇 명 있는지 체크하기 위한 목표 점수이다.

다음과 같이 두 가지 경우를 고려해볼 수 있다.

 

"javabackendjuniorpizza" : [50, 80, 100, 150, 200] 이고 target은 150이라면 target은 배열 안에 존재한다. 

"javabackendjuniorpizza" : [50, 80, 100, 150, 200] 이고 target은 300이라면 target은 배열 안에 존재하지 않는다.

 

아래와 같은 과정으로 이분탐색을 진행한다.

내가 구하고 싶은 것은 target의 위치 즉 인덱스 값이다.

target의 위치를 구해서 arr의 길이에서 빼주면 그 값이 target 이상인 요소들의 갯수랑 똑같기 때문이다.

만약 target이 arr에 존재하지 않는다면 mid + 1을 리턴하고 arr의 길이에서 빼주어야 올바른 값이 나온다.

// 의사코드
arr = [50, 80, 100, 150, 200], target = 150
left = 0
right = 0
mid = (left + right) / 2
while(right >= left){
  if(arr[mid] === target) return mid
  if(arr[mid] < target) left = mid + 1
  else right = mid - 1;
  mid = (left + right) / 2
}

return mid + 1

 

최종 구현

블로그를 참고만 하려고 했는데 완성된 코드를 보니 다 따라친 코드가 되었다.

한 문제에 해시맵과 이진탐색으로 시간복잡도를 줄이는 문제였다. 막혔을 때 어떻게 해결해야할 지 방법이 잘 떠오르지 않았다.

이중 반복문으로 해결이 안되니 해시맵을 사용해볼까? ➡ 탐색의 과정에서 시간이 많이 소요되니 효율적인 이진탐색을 해볼까?

이러한 생각의 흐름이 중요한데 하나의 장애물에 막히니 다음 스텝이 생각나지 않고... 많이 답답했다.

 

그리고 참고한 블로그의 개발자님께서는 이렇게 기능별로 함수를 구현해서 잘 쪼개어 문제를 해결했다. 이런 연습도 자주 해야겠다.

function getInfos(info){
    const infos = {};
    info.forEach(infoString => {
        const arr = infoString.split(" ");
        const score = Number(arr.pop());
        const key = arr.join("");
        if(infos[key]) infos[key].push(score);
        else infos[key] = [score];
    });
    for(const key in infos){
        infos[key].sort((a, b) => a - b);
    }
    return infos;
}

function getResult(infos, query, score){
    let cnt = 0;
    const infosKey = Object.keys(infos);
    return infosKey
    .filter(key => query.every(v => key.includes(v)))
    .reduce((acc, key)=> acc + infos[key].length - binarySearch(infos[key], score), 0);
}

function binarySearch(arr, target){
    let left = 0;
    let right = arr.length - 1;
    let mid = Math.floor((left + right) / 2);
    while(right >= left){
        if(arr[mid] === target) return mid;
        if(arr[mid] < target) left = mid + 1;
        else right = mid - 1;
        mid = Math.floor((left + right) / 2);
    }
    return mid + 1;
}

function solution(info, query) {
    let answer = [];
    const infos = getInfos(info);
    query.forEach((elem)=>{
        let tmp = [];
        let a = elem.split("and");
        a.forEach((c, idx)=>{
            if(idx === 3){
                let b = c.split(" ");
                b.forEach((t) => tmp.push(t));
            }
            else tmp.push(c);
        });
        tmp = tmp.map((elem) => elem.trim()).filter((elem) => elem && elem !== "-");
        const score = tmp.pop();
        const result = getResult(infos, tmp, score);
        answer.push(result);
    });
    return answer;
}