[Programmers] (Javascript) 순위 검색

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

코딩테스트 연습 - 순위 검색

- 최근 풀었던 문제 중 가장 많은 시간을 할애한 것 같다.

 

▶ 코드 : 

let data = new Map();

function makeData(info)
{
    let scores = [];
    for(let s of info)
    {
        s = s.split(' ');
        let arr = s.slice(0,4);
        let score = parseInt(s[4]);
        scores.push(score);
        s= arr.join('');
        if (data.has(s))
        {
            val = data.get(s);
            val = [...val, score]
            data.set(s, val);
        }
        else
        {
            data.set(s,[score]);
        }    
    }

    let keyList = data.keys();

    for (const key of keyList)
    {
        let temp = data.get(key).sort((a,b) => a-b);
        data.set(key, temp);            
    }
}

function solution(info, query) {
    let answer = [];
    makeData(info);

    let keyList = [...data.keys()];
    
    query.map((s) => {
        s = s.split(' ');
        let qScore = s.pop();
        s= s.filter((element) => {if (element !== '-' && element !== 'and'){return true;}});        
        let temp = keyList.filter((key) => s.every(word => key.includes(word)));
        
        let count = 0;
        for (const key of temp)
        {
            let d = data.get(key);
            count += d.length - binarySearch(d, qScore);
        }

        answer.push(count)
    });

    return answer;
}

function binarySearch(arr, score){
    let low = 0;
    let high = arr.length - 1;
    let mid;

    while(low < high)
    {
        mid = Math.floor((low+high) / 2);
        // lower bound 사용 high를 mid -1이 아닌 mid로 설정
        if(arr[mid] >= score)
        {
            high = mid;
        }
        else
        {
            low = mid + 1;
        }
    }

    //만일 arr에 score보다 큰 경우가 없는 경우
    if(arr[high] < score){
        high += 1;
    }
    return high;
}

 

▶ 문제 풀이 :

1. 초기 info에 대하여 문자열을 파싱하고 Map()에 key로 문자열, value로 점수를 저장한다.

  - 이때 value는 점수들의 배열로 저장하며, Map() 초기화가 완료된 후 각 key를 이용해 오름차순 정렬해준다.(이분 탐색을 위해)

2. query 데이터를 파싱하여 해당 query에 포함된 문자열들이 Map()의 key 문자열에 포함되었는지 검사 후 포함하는 키들만을 추출한다. 

3. 이후 추출한 key들에 대해 Map()에서 점수배열을 가져와 이분 탐색을 이용해 원하는 index를 찾고 개수를 구한다.

4. 각 query문에 대하여 반복하며 쿼리문 마다 count한 값을 answer배열에 push 한다.