2019 KAKAO BLIND RECRUITMENT-후보키

06.12에 푼 문제입니다🌷
후보키

function solution(relation) {
    var answer = 0;
    const tuple=[]
    const various=[]
    for(let i=0;i<relation[0].length;i++)
        tuple.push(i)
    for(let i=1;i<=relation[0].length;i++)
        various.push(...getCombination(tuple,i))
        
    //조합으로 튜플 테이블을 만들고 유일성을 체크한다
    const tupleindexlist=[]
    various.map(tupleindex=>{
        const tuplelist=[]
        relation.map(r=>tuplelist.push(matching (r,tupleindex)))
        if(tuplelist.length===[...new Set(tuplelist)].length){
            tupleindexlist.push(tupleindex)
        }
    })
    //희소성 체크
    const answerlist=[]
    answerlist.push(tupleindexlist.shift())
    while(tupleindexlist.length!==0){
        let tmp=true
        let tu=tupleindexlist.shift()
        answerlist.map(a=>{
            if(isSubSetof(a,tu))tmp=false
        })
        
        if(tmp) answerlist.push(tu)
    }
    
    return answerlist.length;
}

//조합
function getCombination(arr,num){
    const result=[]
    if(num===1) return arr.map(x=>[x])
    
    arr.forEach((fixed,index,origin)=>{
        const rest=origin.slice(index+1)
        const combination=getCombination(rest,num-1)
        const attach=combination.map(c=>[fixed,...c])
        
        result.push(...attach)
    })
    
    return result
}


function matching (relation,tupleindex){
    let result=''
    tupleindex.map(t=>{
        result+=relation[t]
    })
    
    return result
}

function isSubSetof(a,b){
    const arr = [...a,...b]
    const setarr=[...new Set(arr)]
   return setarr.length===b.length? true: false
}

좋은 웹페이지 즐겨찾기