[프로그래머스] 후보키 (JS)

풀이 과정

1. 키 조합 만들기
2. 해당 키 조합을 셋에 담으면서 중복되는지 검사
   중복되지 않으면 유일성을 만족한 키 조합에 추가
3. 키 조합 중 이전에 유일성을 만족한 키 조합이 있으면 최소성을 만족하지 못하는 것이므로 제외하기
   (이전 키 조합 중 하나가 현재 키 조합의 부분집합인 경우)

코드

function solution(relation) {
  const col = relation[0].length;
  const arr = Array.from(Array(relation[0].length), (_, i) => i);
  let comb = [];
  for (let i = 0; i < col; i++) {
    comb.push(...combination(arr, i + 1));
  }

  comb = checkUnique(relation, comb);
  comb = checkMinimal(comb);
  return comb.length;
}

function combination(arr, selectNum) {
  if (selectNum === 1) return arr.map((v) => [v]);

  const result = [];
  arr.forEach((fix, i, origin) => {
    const combi = combination(origin.slice(i + 1), selectNum - 1);
    const attach = combi.map((c) => [fix, ...c]);
    result.push(...attach);
  });
  return result;
}

function checkUnique(relation, comb) {
  let result = [];

  comb.forEach((c) => {
    let set = new Set();
    relation.forEach((rel) => set.add(c.map((e) => rel[e]).join(',')));
    if (set.size == relation.length) result.push(c);
  });

  return result;
}

function checkMinimal(comb) {
  let result = [];

  while (comb.length) {
    result.push(comb[0]);
    comb = comb.reduce((a, c) => {
      if (!comb[0].every((e) => c.includes(e))) a.push(c);
      return a;
    }, []);
  }

  return result;
}

🤔

절망.. 정말이라고 치려고 했는데 마음의 소리가 이렇게 밖으로.. 최초로 포기하고 싶었던 문제 ㅎㅎㅎ
어찌어찌 재귀로 1시간 붙잡고 있었는데 아무리 해도 테케 반밖에 통과를 못하고 왜인지는 모르겠고...
결국 다른 사람 풀이를 참고했다.
그러고서도 일단 조합 재귀에서부터 보기 싫어져서 내일로 미룰까 하다가 저녁 먹고 와서 종이에 하나씩 그려가면서 이해를 했다. 다시 풀려면 코드를 거의 외워야 할 듯..
휴... 알고리즘 공부에 이렇게 시간 많이 쓰는 게 맞나... 면접이 코앞인데...