[프로그래머스] 카카오 - 후보키

문제

2019 카카오 블라인드 채용 - 후보키

https://school.programmers.co.kr/learn/courses/30/lessons/42890

 

 

풀이

설명

후보 키의 개수를 구하는 문제입니다.

 

모든 조합에 대해서 유일성과 최소성을 만족하는 조합의 개수를 구합니다.

 

예시 코드

function solution(relation) {
  const candidateKeys = [];
  const numRows = relation.length;
  const numCols = relation[0].length;

  for (let i = 1; i < 1 << numCols; i++) {
    const comb = [];
    for (let j = 0; j < numCols; j++) {
      if (i & (1 << j)) comb.push(j);
    }

    if (isUnique(comb) && isMinimal(comb)) candidateKeys.push(comb);
  }

  return candidateKeys.length;

  function isUnique(comb) {
    const rowsMap = new Set();
    for (let r = 0; r < numRows; r++) {
      const tuple = comb.map((index) => relation[r][index]).join("|");
      if (rowsMap.has(tuple)) return false;
      rowsMap.add(tuple);
    }

    return true;
  }

  function isMinimal(comb) {
    for (const key of candidateKeys) {
      if (key.every((k) => comb.includes(k))) return false;
    }

    return true;
  }
}