2019 KAKAO BLIND RECRUITMENT) 후보키 - Javascript 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/42890?language=javascript 

프로그래머스

문제의 핵심은 유일성을 만족하지 못하는 index를 추려내어 그것들의 조합으로 최소성을 만족하는 후보키를 구하는 것입니다.

만약 유일성을 만족하지 못하는 항목이 5개 있다면 2개 ~5개의 조합을 전부 확인하고 그 과정에서 최소성을 만족하는지, 후보키로 등록할 수 있는지를 탐색하는 과정으로 코드를 작성하였습니다.

function solution(relation) {
  var answer = 0;
  const arr = []; // 후보키의 index
  const mini = []; // 정답이 되는 후보키의 배열
  function minimality(arr) {
    // 후보키가 최소성을 만족하는지 확인합니다.
    for (let x of mini) {
      let check = 0;
      for (let y of x) {
        if (!arr.includes(y)) {
          check = 1;
          break;
        }
      }
      if (check === 0) return false;
    }
    return true;
  }
  for (let i = 0; i < relation[0].length; i++) {
    // 유일성이 될 수 있는 키 구하기
    const set = new Set();
    for (let j = 0; j < relation.length; j++) {
      if (set.has(relation[j][i])) {
        // 값이 겹치면 유일성을 만족할 수 없으므로 배열의 조합으로 탐색해야합니다.
        // 유일성이 안되는 index를 arr에 넣어줍니다.
        arr.push(i);
        break;
      } else set.add(relation[j][i]);
    }
    if (set.size === relation.length) answer++;
  }
  for (let i = 2; i <= arr.length; i++) {
    const target = [];
    function DFS(L, m) {
      if (L === i) {
        if (minimality(target)) {
          const set = new Set();
          for (let x of relation) {
            let arr3 = "";
            for (let y of target) {
              arr3 += x[y];
            }
            if (set.has(arr3)) break;
            else set.add(arr3);
          }
          if (set.size === relation.length) {
            mini.push(target.slice());
            answer++;
          }
        }
      } else {
        for (let j = m; j < arr.length; j++) {
          target.push(arr[j]);
          DFS(L + 1, j + 1);
          target.pop();
        }
      }
    }
    DFS(0, 0);
  }
  return answer;
}