(프로그래머스 KAKAO c++)순위 검색

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

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

주어진 info 배열과 query 배열을 토크나이징 하여 정답을 찾아내면 된다.

 

우선 info 배열을 공백 기준으로 split() 함수 실행.

이후 최소 단위로 이뤄진 단어와 "-"를 조합하여 모든 가능성을 map에 저장한다.

그렇기 때문에 for of문이 4중 중첩이 되고, 한 사람 당 "-"를 포함한 모든 쿼리문을 저장하게 된다.

 

map에 모든 가능성을 저장한 후, 점수별로 정렬이 필요하다.

내림차순으로 정렬을 실행하여, 이후 이진 탐색을 진행할 수 있도록 만든다.

 

이제 query 또한 토크나이징 한다.

and와 공백을 지우고, 조건과 점수를 나눈다.

저장한 map에서 조건에 해당하는 value를 가져온다.(없으면 빈 배열)

front와 back을 이용해 이진 탐색을 진행하여, 현재 query문의 점수보다 높은 사람들을 카운팅하면 된다.

const solution = (info, query) => {
    const answer = [];
    const infoParsingData = new Map();
    const queryParsingData = [];
    
    // info 데이터 파싱
    for(let i = 0; i < info.length; i++){
        const data = info[i].split(" ");
        const string = Array.from({length: 4}, () => Array(2).fill("-"));
        const score = parseInt(data.splice(4));
        
        for(let j = 0; j < 4; j++){
            string[j][0] = data[j];
        }
        
        for(const lang of string[0]){
            for(const position of string[1]){
                for(const career of string[2]){
                    for(const food of string[3]){
                        const key = lang + position + career + food;
                        const value = infoParsingData.has(key) ? infoParsingData.get(key) : [];
                        
                        value.push(score);
                        infoParsingData.set(key, value);
                    }
                }
            }
        }
    }
    
    // infoParsingData 정렬
    for(const [_, value] of infoParsingData){
        value.sort((a, b) => b - a);
    }
    
    // query 데이터 파싱 및 답 찾기
    for(let i = 0; i < query.length; i++){
        const data = query[i].split(/\sand\s/).join("").split(" ");
        const score = parseInt(data.splice(1));
        const condition = data.join("");
        const correctData = infoParsingData.has(condition) ? infoParsingData.get(condition) : [];
        let front = 0;
        let back = correctData.length - 1;
        
        while(front <= back){
            const mid = Math.floor((front + back) / 2);
            
            if(correctData[mid] >= score){
                front = mid + 1;
            } else{
                back = mid - 1;
            }
        }
        
        answer.push(front);
    }
    
    return answer;
}