후보키

문제 링크

문제 요약

• 관계 데이터베이스에서 릴레이션(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
}