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
}