[JS] 후보키

문제

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

프로그래머스

 

풀이

이 문제를 풀이하는 흐름은 나올 수 있는 조합을 구한뒤 조합별 데이터가 유니크한지 검증하고, 그 다음 미니멀한지 체크하면 된다.

 

조합의 경우 재귀적으로 조합을 구할 수 있게 풀이한다.

function makeCombination(num, arr) {
  let result = [];
  if (num === 1) {
    return arr.map(a => [a])
  }
  arr.forEach((fix, i, origin) => {
    const rest = origin.slice(i + 1);
    const combi = makeCombination(num - 1, rest);
    const attach = combi.map((c) => [fix, ...c]);
    result.push(...attach);
  })
  return result;
}

 

조합을 구했다면 유니크 체크를 진행하면 된다.

function checkUniq(relation, combination) {
  const result = [];
    
  combination.forEach(comb => {
    let set = new Set();
        
    relation.forEach(e => {
      set.add(comb.map(el => e[el]).join(', '));
    });
        
    if (set.size === relation.length) result.push(comb);
  });
  return result;
}

유니크 검사시 주의할 점은 중복된 데이터의 경우 Set 객체에 저장하기 때문에 이전에 중복된 데이터가 사라지기 때문에 크기 비교를 진행해 유니크한지 검사해야한다.

 

이렇게 구해진 유니크 조합을 이용해 미니멀을 체크해줘야 한다.

function checkMinimal(combinations) {
  let result = [];
    
  while (combinations.length) {
    result.push(combinations[0]);
        
    combinations = combinations.reduce((acc, cur) => {
      let notMinimal = combinations[0].every(e => cur.includes(e));
      if (!notMinimal) acc.push(cur);
      return acc;
    }, []);
  }
  return result;
}

미니멀의 경우 맨 앞의 요소와 나머지 요소들의 종속 여부를 검사해 포함되지 않는다면 미니멀한 조합임을 검사해야한다. 

 

코드

function solution(relation) {
  let idxArr = Array.from({ length: relation[0].length }, (v, i) => i);
  let combinationArr = [];
    
  for (let i = 0; i < idxArr.length; i++) {
    combinationArr.push(...makeCombination(i + 1, idxArr));
  }
    
  combinationArr = checkUniq(relation, combinationArr);
  return checkMinimal(combinationArr).length;
}

function makeCombination(num, arr) {
  let result = [];
  if (num === 1) {
    return arr.map(a => [a])
  }
  arr.forEach((fix, i, origin) => {
    const rest = origin.slice(i + 1);
    const combi = makeCombination(num - 1, rest);
    const attach = combi.map((c) => [fix, ...c]);
    result.push(...attach);
  })
  return result;
}

function checkUniq(relation, combination) {
  const result = [];
    
  combination.forEach(comb => {
    let set = new Set();
        
    relation.forEach(e => {
      set.add(comb.map(el => e[el]).join(', '));
    });
        
    if (set.size === relation.length) result.push(comb);
  });
  return result;
}

function checkMinimal(combinations) {
  let result = [];
    
  while (combinations.length) {
    result.push(combinations[0]);
        
    combinations = combinations.reduce((acc, cur) => {
      let notMinimal = combinations[0].every(e => cur.includes(e));
      if (!notMinimal) acc.push(cur);
      return acc;
    }, []);
  }
  return result;
}