알고리즘 풀이 - 후보키
January 09, 2021
후보키
문제 요약
-
관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
- 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
- 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.
제한사항
- relation은 2차원 문자열 배열이다.
- relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
- relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
- relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
- relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)
Input
- 릴레이션을 나타내는 문자열 배열 relation
output
- 이 릴레이션에서 후보 키의 개수를 return
해결방법
- 모든 키 조합을 생성한다.
-
키 조합을 꺼내보면서 해당 키가 후보키가 될 수 있는지 확인한다.
- 중복된 요소가 없는가? (해당 키로 아이템을 꺼내보고
Set을 했을 때 전체 크기와 동일한가?)
- 중복된 요소가 없는가? (해당 키로 아이템을 꺼내보고
-
해당 키가 후보키라면
count를 +1 한다- 전체 조합에서 해당 키를 포함하는 키를 삭제한다.
- 전체 순회를 하고 난 이후
count를 반환한다
let combinationArr = []
function combinations(ref, src, targetLen) {
if (src.length === targetLen) combinationArr.push(src)
else {
ref.map((element, i) => {
const newSrc = src.slice(0)
newSrc.push(element)
combinations(ref.slice(i + 1), newSrc, targetLen)
})
}
}
function solution(relation) {
const row = relation.length
const col = relation[0].length
const ref = [...new Array(col).keys()]
for (let i = 1; i <= col; i++) {
combinations(ref, [], i)
}
let count = 0
while (combinationArr.length) {
const key = combinationArr.shift()
const set = new Set(
relation.map(r => {
return key
.map(k => {
return r[k]
})
.join(' ')
})
)
if (set.size === row) {
count++
combinationArr = combinationArr.filter(
element => !key.every(v => element.includes(v))
)
console.log(combinationArr)
}
}
return count
}