[카카오 2019 blind] 후보키

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

코딩테스트 연습 - 후보키

처음 코드

function solution(relation) {
    function comb(l,n){
        if(n<=0) return [[]];
        else if(l.length==0) return [];
        let w = comb(l.slice(1),n-1).map(x=>{x.push(l[0]); return x});
        let wo = comb(l.slice(1),n);
        return w.concat(wo);
    }

    function subset(a,b){
        // a 가 b 의 부분집합인가?
        return a.every(x=>b.includes(x));
    }

    let students = relation.length;
    let attr = []
    for(let i=0; i<relation[0].length; i++) attr.push(i);

    let res = [];
    for(let n=1; n<=attr.length ; n++){
        let keys = comb(attr,n);
        for(let k of keys){
            // 유일성 테스트
            if(relation.reduce((s,tuple)=>s.add(k.reduce((a,i)=>a+tuple[i],"")), new Set()).size < students) continue;
            // 최소성 테스트
            if(res.some(ckey=>subset(ckey,k))) continue;
            res.push(k);
        }

    }
    console.log(res);
    return res.length;
}

 

 

비트마스크 적용한 풀이

function solution(relation) {
    let row = relation.length;
    let col = relation[0].length;

    // 가능한 인덱스 조합 1 ~ (1<<col -1) => candidate key 후보
    let res =[];
    for(let key=1; key<(1<<col); key++){
        //1. 최소성 검사 : 이미 res에 들은 것들이 i의 부분집합이지 않을 것.
        //x&i == x이면 부분집합.
        if(res.some(x=>(x&key)==x)) continue;
        //2. 유일성 검사 
        let set = new Set();
        for(let tuple of relation){
            let value="";
            for(let i=0; i<col; i++){
                value+= ((key>>i)&1)==1 ? tuple[i] : "";
            }
            set.add(value);
        }
        if(set.size < row) continue;

        //1,2 통과한 키
        res.push(key);
    }
    return res.length;
}

다른 사람들 풀이 보니까 다 비트마스크로 풀었길래 참고해서 바꿔봤는데 실행시간이 훨씬 단축됐다.

 

🤠 적용한 개념

[1] 원소 n개인 집합의 부분집합 (혹은 가능한 모든 조합) 표현 [0, 2<<n)

유효한 candidate key들이 담긴 res 배열 중 새로 검사 중인 키의 부분집합인 것이 없을 것. 

이라는 방식으로 최소성 검사를 하기 위해 

(예를 들어 res = ["BC"] 면 검사중인 key "BCD"는 탈락이다)

처음 코드에서는 키 검사를 n=1인 것, 2인것, 3인 것 ... 이 순서로 했는데

("BCD"를 먼저 검사하고 "BC"를 검사하면 둘다 통과해버리니까)

 

비트마스크 방식으로 그냥 key = 1 ~ 2^n 순서대로 하면

자기가 포함하고 있는 1들 중 일부만 포함하는 (부분집합인) 애들은 항상 본인보다 낮은 숫자라 먼저 검사된다.

그니까 걍 하면 됨.

 

 

[2] a가 b의 부분집합에 해당하는 경우인지 확인하기 a&b==a ?

 

[3] 2진수 오른쪽 끝에서부터 i번째 인덱스 숫자 구하기  (n>>i)&1