프로그래머스 LEVEL 2(후보키)

사용 언어 : javascript
해결 날짜 : 2023-04-18
해결 방법 :
- 조합을 활용해 문제 해결
  - 주어진 relation으로 만들 수 있는 key의 모든 조합을 돌며
  - 유일성과 최소성을 만족할 때 answer 증가
회고 :
- x

코드

const getCombinations = (arr, selectNumber) => {
  const results = [];
  if (selectNumber === 1) return arr.map((el) => [el]);

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest, selectNumber - 1);
    const attached = combinations.map((el) => [fixed, ...el]);
    results.push(...attached);
  });

  return results;
};

function solution(relation) {
  let answer = 0;
  const columns = Array.from({ length: relation[0].length }, (_, i) => i);
  const combinations = [];
  const pass = [];

  for (let i = 1; i <= columns.length; i++) {
    combinations.push(...getCombinations(columns, i));
  }

  combinations.forEach((comb) => {
    if (pass.some((p) => p.filter((v) => comb.includes(v)).length === p.length)) {
      return;
    }

    const key = relation.flatMap((val) => comb.map((item) => val[item]).join(''));
    if (new Set(key).size === key.length) {
      pass.push(comb);
      answer++;
    }
  });

  return answer;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges