🔎 후보키
❓ 문제링크
https://programmers.co.kr/learn/courses/30/lessons/42890
📄 제출 코드
function solution(relation) {
var answer = 0;
let combList = [];
for (let i = 0; i < relation[0].length; i++) {
combList.push(i);
}
for (let i = 1; i <= combList.length; i++) {
makeCombi(combList, i, 0);
}
// console.log(combi);
let keyList = [];
for (let i = 0; i < combi.length; i++) {
checkCombi(keyList, combi[i], relation);
}
answer = keyList.length;
return answer;
}
function checkIsUnique(key, relation, arr=[]) {
let isUnique = true;
for (let i = 0; i < relation.length; i++) {
let findEl = arr.find(el => {
let flag = true;
for (let j = 0; j < key.length; j++) {
if (el[key[j]] != relation[i][key[j]]) flag = false;
}
return flag;
})
if (findEl !== undefined) isUnique = false;
else arr.push(relation[i]);
}
return isUnique;
}
function checkIsMin(keyList, key) {
let isMin = true;
for (let i = 0; i < keyList.length; i++) {
let prev = keyList[i];
for (let j = 0; j < key.length; j++){
prev = prev.filter(el => el !== key[j]);
}
if (prev.length == 0) isMin = false;
}
return isMin;
}
function checkCombi(keyList, key, relation) {
// 최소성 : 이미 등록된 후보키 배열을 포함하는 배열이 하나라도 존재하면 x
let isMin = checkIsMin(keyList, key) ;
// 유일성 : 키로 사용했을때 하나라도 중복되면 x
let isUnique = checkIsUnique(key, relation);
if (isMin && isUnique) keyList.push(key);
}
let combi = [];
function makeCombi(comb, n, depth, arr = []) {
if (n == depth) combi.push([...arr]);
else {
for (let i = 0; i < comb.length; i++) {
arr.push(comb[i]);
makeCombi(comb.slice(i+1), n, depth + 1, arr);
arr.pop();
}
}
}
let relation = [["100", "ryan", "music", "2"], ["200", "apeach", "math", "2"], ["300", "tube", "computer", "3"], ["400", "con", "computer", "4"], ["500", "muzi", "music", "3"], ["600", "apeach", "music", "2"]]
console.log(solution(relation));처음에 조합을 이용해야겠다는 생각은 들었는데 문제 이해를 못해서 최소성과 유일성의 구현을 못했다. 그래서 다른 사람의 코드를 보고 이렇게 구현하라는 거구나 라고 이해하고, 참고하여 다시 작성하였다.
👉 조합 만들기
먼저, relation길이 즉, 컬럼 수 만큼의 배열을 가지고 조합을 만들기 위해 컬럼수를 배열에 1씩 증가하며 push한다.
for (let i = 0; i < relation[0].length; i++) {
combList.push(i);
}그리고 조합을 만드는 makeCombi메소드를 작성한다.
반복문을 통해 요소가 1개 2개 ... combList수인 조합을 만든다.
let combi = [];
function makeCombi(comb, n, depth, arr = []) {
if (n == depth) combi.push([...arr]);
else {
for (let i = 0; i < comb.length; i++) {
arr.push(comb[i]);
makeCombi(comb.slice(i+1), n, depth + 1, arr);
arr.pop();
}
}
}👉 keyList만들기
keyList 만들기 위해 checkCombi메소드를 작성한다.
거기서 최소성을 검사하는 checkIsMin메소드와 유일성을 검사하는 checkIsUnique를 작성하여
두개의 메소드가 true인 경우 key를 keyList에 추가 할 것이다.
function checkCombi(keyList, key, relation) {
// 최소성 : 이미 등록된 후보키 배열을 포함하는 배열이 하나라도 존재하면 x
let isMin = checkIsMin(keyList, key) ;
// 유일성 : 키로 사용했을때 하나라도 중복되면 x
let isUnique = checkIsUnique(key, relation);
if (isMin && isUnique) keyList.push(key);
}👉 최소성 검사
최소성은 이미 등록된 후보키 배열을 포함하는 배열이 하나라도 존재하면 x.
keyList에서 key배열을 하나 꺼내 들고온 key[j]와 다른 배열들을 뽑아 만약 다른 배열이 없으면 false를 리턴한다.
function checkIsMin(keyList, key) {
let isMin = true;
for (let i = 0; i < keyList.length; i++) {
let prev = keyList[i];
for (let j = 0; j < key.length; j++){
prev = prev.filter(el => el !== key[j]);
}
if (prev.length == 0) isMin = false;
}
return isMin;
}👉 유일성 검사
유일성은 키로 사용했을때 하나라도 중복되면 x.
function checkIsUnique(key, relation, arr=[]) {
let isUnique = true;
for (let i = 0; i < relation.length; i++) {
let findEl = arr.find(el => {
let flag = true;
for (let j = 0; j < key.length; j++) {
if (el[key[j]] != relation[i][key[j]]) flag = false;
}
return flag;
})
if (findEl !== undefined) isUnique = false;
else arr.push(relation[i]);
}
return isUnique;
}arr에있는 요소와 relation을 하나씩 돌면서 그 안의 key요소와 다르면 false, 아니면 true를 리턴하여 같은 요소의 배열을 만든다.
findEl이 undefined가 아니면 뭔가 찾은게 있다는 것이기 때문에 isUnique를 false로 바꾸고 아니라면 중복되지 않으니 relation[i]를 arr에 넣고 다음 반복을 진행한다.
📘 참고
