[Javascript/자바스크립트] (프로그래머스) 후보키

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

코드

function solution(relation) {
  const answer = [];

  const dfs = (idx, picked) => {
    if (idx === relation[0].length) {
      const result = relation.reduce((acc, cur) => {
        acc.add(cur.filter((_, i) => picked.has(i)).join("_"));
        return acc;
      }, new Set());

      if (result.size === relation.length) {
        answer.push(new Set(picked));
      }
      return;
    }

    dfs(idx + 1, picked);
    picked.add(idx);
    dfs(idx + 1, picked);
    picked.delete(idx);
  };

  dfs(0, new Set());

  const remove_set = new Set();

  for (let i = 0; i < answer.length - 1; i++) {
    for (let j = i + 1; j < answer.length; j++) {
      const intersection = new Set(
        [...answer[i]].filter((x) => answer[j].has(x))
      );

      if (intersection.size === answer[i].size) {
        remove_set.add(j);
      } else if (intersection.size === answer[j].size) {
        remove_set.add(i);
      }
    }
  }
  return answer.length - remove_set.size;
}

 

우선 DFS()를 활용하여 가능한 키의 조합을 모두 구한다. idx === n까지 돌아서 가능한 조합을 구했다면 해당 조합으로 후보키를 레코드를 유일하게 식별할 수 있는 조합(유일키)을 만들 수 있는지 알아본다. 

const result = relation.reduce((acc, cur) => {
    acc.add(cur.filter((_, i) => picked.has(i)).join("_"));
    return acc;
}, new Set());

if (result.size === relation.length) {
	answer.push(new Set(picked));	
}

 

유일하게 식별할 수 있는 조합인지 판별하는 방법은 다음과 같다.

 

`picked`(선택된 컬럼들)의 값을 하나의 문자열로 묶은 값들의 집합을 구하고, 이 집합의 길이가 원본 배열의 길이와 같은지 확인하면 된다.

 

그리고 마지막으로는 위의 과정을 통해 모은 유일키들에서 최소성을 갖는 조합을 찾아내면 된다. 최소성 있는 조합을 가려내는 방법은 다음과 같다.

for (let i = 0; i < answer.length - 1; i++) {
    for (let j = i + 1; j < answer.length; j++) {
      const intersection = new Set(
        [...answer[i]].filter((x) => answer[j].has(x))
      );

      if (intersection.size === answer[i].size) {
        remove_set.add(j);
      } else if (intersection.size === answer[j].size) {
        remove_set.add(i);
      }
    }
  }

 

한 조합이 다른 조합의 부분집합일 때, 더 큰 조합은 최소성을 갖지 않는 조합이므로 삭제 대상(remove_set)에 추가한다.

 

유일키들의 조합의 크기에서 최소성을 만족하지 않는 집합들의 크기를 빼면 바로 답이다.