[프로그래머스] Lv2. 후보키 - JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 후보키

문제

제한사항

📌 내가 생각한 풀이

1. 조합을 이용하여 후보키를 잡을 Column 조합을 구한다.
2. 조합에서 나온 경우의 수로 튜플을 구한다.
3. 튜플 중 중복되는 것이 없는 원소들을 used에 넣는다. (유일성 만족)
4. 원소

들 중에서 최소성을 만족하는지 체크한뒤 만족하면 answer++
최소성 만족은 두 개의 집합을 교집합을 하여 두개중 크기가 더 큰 집합의 크기보다 크면 만족, 크기가 같거나 작으면 만족하지 못한다.

const gyo = (str1, str2) =>{
    let splited1 = str1.split('');
    let splited2 = str2.split('');
    let len = Math.max(str1.length, str2.length)
    let set = new Set(splited1.concat(splited2));
    return set.size > len ? true : false;
}

const getCombination = (arr, selectNum) =>{
    let result = [];
    if(selectNum === 1) return arr.map((d)=>[d]);
    arr.forEach((fixed,idx,origin)=>{
        let rest = origin.slice(idx+1)
        let combination = getCombination(rest, selectNum-1);
        let attached = combination.map((data)=>[fixed, ...data]);
        result.push(...attached)
    })
    return result;
}

function solution(relation) {
    var answer = 0;
    let used = [];
    let entire = relation.length;
    let columnNum = relation[0].length;
    let numArr = [];
    let fixed = [];
    let checkArr = new Array(columnNum).fill(true)
    for(var k = 0; k<columnNum; k++){
        numArr[k] = k;
    }
    for(var i =1; i<=columnNum; i++){
        let selectNum = i;
        let combination = getCombination(numArr, selectNum);
        combination.forEach((d,i)=>{
            let set = new Set();
            let check = true;
            for(var k =0; k<entire; k++){
                let str = '';
                for(var j =0; j<d.length; j++){
                    str += `${relation[k][d[j]]}/`;
                }
                set.add(str);
            }
            if(set.size === entire){
                let indexNum ='';
                d.map((data)=>indexNum+=data)
                used.push(indexNum);
            }
        })
    }
    used.forEach((data,idx,origin)=>{
        let val = data;
        if(fixed.length === 0) fixed.push(data);
        else{
            let check = true;
            for(var i =0; i<fixed.length; i++){
                check = check && gyo(fixed[i],val)
            }
            if(check){
                fixed.push(val)
            }
        }
    })
    return fixed.length
}

📌 느낀점

최소성을 만족하는데 생각을 잘못해서 오래걸렸다. 만약 013 과 134면 둘다 정답으로 인정을 해주어야한다. 여기서 나는 교집합 방식을 이용하여 최소성을 구해주었다.