우선 인풋범위가 매~~우 작기 때문에 완탐으로 풀어도, O(N^3)으로 풀어도 차고 넘친다고 생각을 했다.
[["100","ryan","music","2"],
["200","apeach","math","2"],
["300","tube","computer","3"],
["400","con","computer","4"],
["500","muzi","music","3"],
["600","apeach","music","2"]]
그래서 이런식으로 되어있는 relation 인풋에 대해서 우선 유일성과 최소성을 고려하지 않고
나올 수 있는 모든 후보키 조합을 생각해보기로 한다.
여기서는 키의 명칭을 학번,이름,전공,학년
으로 표시할 수 있었지만
우리가 문제를 풀때는 인풋에 따라서 100이 학번인지 ryan이 이름인지 알 수 없기때문에 그냥 인덱스값으로 구분하도록 하자.
Ex)
[0,1,2,3]
으로 만들 수 있는 키 조합을 생각한다.조합과 순열을 구하는 방법은 이곳에 따로 정리를 해보았다.
[0,1,2,3]에서 나올 수 있는 조합의 경우의 수는 아래와 같다.
combinations=
[
[ 0 ], [ 1 ],
[ 2 ], [ 3 ],
[ 0, 1 ], [ 0, 2 ],
[ 0, 3 ], [ 1, 2 ],
[ 1, 3 ], [ 2, 3 ],
[ 0, 1, 2 ], [ 0, 1, 3 ],
[ 0, 2, 3 ], [ 1, 2, 3 ],
[ 0, 1, 2, 3 ]
]
combinations
배열과 문제에서 정의된 relation
을 함수의 인자로 받는다.combinations
배열을 순회해나가며 조합 하나하나씩 유일성을 만족하는지 검사한다.relation
배열에서 현재 순회중인 combinations 조합으로 후보키를 만들어서 중복을 허용하지 않는 자료구조인 set에 넣어본다.아래 주석을 보면 좀 더 이해하기 쉽다!
function checkUniqueness(relation,combinations){
let results = []; // 유일성을 만족하는 조합들로만 이루어진 results 배열
combinations.forEach((combination) => {
let set = new Set();
relation.forEach((rel) => {
set.add(combination.map(combi => rel[combi]).join(','));
// ex) 현재 조회중인 combination을 [1,3]이라고 하면, combi는 1,3 각각 그 원소를 뜻함
// 중첩반복문이 많아서 O(N^3)인데, 입력범위가 매~우 적어서 이정도면 효율성 매우 충분함
});
// 이때 만들어지는 Set은 relation 배열을 순회해나가면서 인덱스 1번째와 3번째를 합친
// { 'ryan,2', 'apeach,2', 'tube,3', 'con,4', 'muzi,3' }의 형태임
// 해당 set은 relation의 길이인 6보다 작기때문에 중복이 존재했던것임. 유일성 만족 x
if(set.size == relation.length){
results.push(combination);
}
});
return results;
}
문제에서는 너무 길게 설명해놓았는데,
후보키들을 순회해나가면서 이미 앞에 등록된 후보키의 배열을 포함하는 배열이 하나라도 존재하면 최소성을 만족시키지 않는다는것을 유의하면 된다.
function checkMinimality(combinations){
let results=[]; // 최소성을 만족하는 조합들로만 이루어진 results 배열
while(combinations.length){
results.push(combinations[0]);
// 유일성을 만족하는 조합중 첫번째 원소를 최소성을 만족하는 원소로 넣는다.
combinations=combinations.reduce((acc,cur)=>{
let notMinimal=combinations[0].every(combination=>cur.includes(combination));
// 현재 조회중인 cur배열 안에 combinations[0]의 모든 원소가 포함된다면 최소성을 만족하지 않는것임
if(!notMinimal) acc.push(cur);
// 최소성을 만족하는 cur 조합을 acc에 추가해줌
return acc;
},[])
// combinations들은 combinations[0]과 비교해서 최소성을 만족하는애들로 갱신됨
}
return results;
}
function solution(relation) {
let answer = 0;
// relation[0]의 길이만큼 인덱스번호를 원소로 가지는 초기배열을 만든다.
let idxArr = Array.from(Array(relation[0].length), (v, i) => i);
let combinations=[]; //가능한 후보키들의 모든 조합을 우선 넣기
for(let i=0;i<idxArr.length;i++){
combinations.push(...getCombination(idxArr,i+1))
}
combinations = checkUniqueness(relation, combinations); //유일성 체크해서 갱신
combinations = checkMinimality(combinations); // 최소성 체크해서 갱신
return combinations.length
}
function checkUniqueness(relation,combinations){
let results = [];
combinations.forEach((combination) => {
let set = new Set();
relation.forEach((rel) => {
set.add(combination.map(combi => rel[combi]).join(','));
});
if(set.size == relation.length){
results.push(combination);
}
});
return results;
}
function checkMinimality(combinations){
let results=[];
while(combinations.length){
results.push(combinations[0]);
combinations=combinations.reduce((acc,cur)=>{
let notMinimal=combinations[0].every(combination=>cur.includes(combination));
if(!notMinimal) acc.push(cur);
return acc;
},[])
}
return results;
}
function getCombination(arr,selectNum){
let result=[];
if(selectNum===1){
return arr.map(a=>[a])
}
arr.forEach((fix,i,origin)=>{
const rest=origin.slice(i+1);
const combi=getCombination(rest,selectNum-1);
const attach=combi.map((c)=>[fix,...c]);
result.push(...attach)
})
return result;
}
level2인데 어려워..ㅠㅠ....🥺