문제 설명 및 링크

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

나의 풀이

info 에 대한 Map 을 먼저 만들고, query 를 돌면서 Map 을 참조해 각각에 대한 개수를 구한다.

결국 query.length x Map 참조 & 개수 계산 로직 만큼 시간이 소요되므로, Map 을 어떻게 구성하고 Map 을 사용해 어떻게 개수를 구할 것인가가 포인트... 인듯?

정확성은 다 통과했는데 효율성에서 계속 fail 떠서 고생하다가 ㅜㅜ, 결국 다른 사람들의 질문을 참조해 문제를 풀었다.

결론은 Map 구성시 각 경우에 대해 array 로 생성 & 정렬하고, 이진법 탐색을 통해 개수를 구한다. (이 이진법 탐색이 생각이 안나서 고생했슴다ㅜㅜ 늙긴 늙었나 보다)

다른 사람 풀이 (bit field, mask 사용)

생각지도 못한 풀이가 있어서 되게 인상 깊었다. 참 능력자가 많은 것 같다.

이런 분들 볼때마다 내 자신이 조그마하게 느껴지기도 하고 부럽기도 한다.

여튼 배울점이 많음.

https://github.com/yuneg11/Programmers-Solutions/tree/master/solutions/72412%20-%20%EC%88%9C%EC%9C%84%20%EA%B2%80%EC%83%89

코드

모든 프로그래머스 문제 관련 코드들은 GitHub 링크 에 있음.

const checkMap = (map, info) => {
    const arr = info.split(' ');
    const num = Number(arr[4]);
    
    const condition = arr.slice(0, 4);
    let arrCondition = [condition.join(' ')];
    
    arrCondition.push(`- ${condition[1]} ${condition[2]} ${condition[3]}`);
    arrCondition.push(`${condition[0]} - ${condition[2]} ${condition[3]}`);
    arrCondition.push(`${condition[0]} ${condition[1]} - ${condition[3]}`);
    arrCondition.push(`${condition[0]} ${condition[1]} ${condition[2]} -`);
    
    arrCondition.push(`- - ${condition[2]} ${condition[3]}`);
    arrCondition.push(`- ${condition[1]} - ${condition[3]}`);
    arrCondition.push(`- ${condition[1]} ${condition[2]} -`);
    arrCondition.push(`${condition[0]} - - ${condition[3]}`);
    arrCondition.push(`${condition[0]} - ${condition[2]} -`);
    arrCondition.push(`${condition[0]} ${condition[1]} - -`);
    
    arrCondition.push(`- - - ${condition[3]}`);
    arrCondition.push(`- - ${condition[2]} -`);
    arrCondition.push(`- ${condition[1]} - -`);
    arrCondition.push(`${condition[0]} - - -`);
    
    arrCondition.push(`- - - -`);
    
    arrCondition.map(c => {
        if (!map[c]) {
            map[c] = [];
        }
        
        map[c].push(num);
    });
};

function solution(info, query) {
    const result = [];
    
    const map = {};
    
    const infos = info.map(i => {
        checkMap(map, i);
    });
    
    for (const key in map) {
        map[key] = map[key].sort((m1, m2) => m1 > m2 ? 1 : -1);
    }
    
    return query.map(q => {
        const arr = q.replace(/ and /g, ' ').split(' ');
        
        const num = Number(arr[4]);
        
        const condition = arr.slice(0, 4).join(' ');
        
        const targets = map[condition] || [];
        
        let start = 0;
        let end = targets.length - 1;
        let center = Math.floor((start + end) / 2);
        let temp = targets.length;
        
        while (start <= end) {
            center = Math.floor((start + end) / 2);
            
            if (targets[center] >= num) {
                temp = center;
                end = center - 1;
            } else {
                start = center + 1;
            }
        }
        
        const result = targets.length - temp;
        
        return result < 0 ? 0 : result;
    });
}