90. 후보키 Javascript

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

프로그래머스

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 후보 키의 개수를 return
• 주어진 자료는 무엇인가?
   - relation : 릴레이션을 나타내는 문자열 배열
• 조건은 무엇인가?
   - relation은 2차원 문자열 배열이다.
   - relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
   - relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
   - relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
   - relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?

1. 모든 후보키 조합을 구한다
2. 이중에서 유일한 후보키 조합을 찾는다 (유일성)
3. 이중에서 최소 후보키 조합을 찾는다 (최소성)

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

const isMinimality = (keys, columns) => !keys.some(it => it.every(it => columns.includes(it)));

const isUnique = (rows, columns) => {
  const map = {};
  const r = rows.map(row => columns.reduce((acc, cur) => acc + row[cur], ''));
  for (let i = 0; i < r.length; i++) {
    if (map[r[i]]) {
      return false;
    }

    map[r[i]] = true;
  }

  return true;
};

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;
};

const getAllKeys = (columnsCount) => {
  const r = [];

  const arr = Array.from({ length: columnsCount }, (_, index) => index);
  for (let i = 0; i < columnsCount; i++) {
    r.push(getCombinations(arr, i + 1));
  }

  return r.flat();
};



const solution = (relation) => {
  // 모든 후보키의 후보를 구하라
  const keys = getAllKeys(relation[0].length);

  const k = keys.reduce((keyList, columns) => {
    // 해당 후보키가 최소성을 만족하는지 확인한다.
    if (!isMinimality(keyList, columns)) {
      return keyList;
    }

    // 해당 후보키가 유일성을 만족하는지 확인한다.
    if (isUnique(relation, columns)) {
      return [...keyList, columns];
    }

    return keyList;
  }, []);

  // 후보키 갯수를 반환한다.
  return k.length;
};

test('candidateKey', () => {
  expect(solution([["100", "ryan", "music", "2"], ["200", "apeach", "math", "2"], ["300", "tube", "computer", "3"], ["400", "con", "computer", "4"], ["500", "muzi", "music", "3"], ["600", "apeach", "music", "2"]])).toEqual(2);
});

 

 

이 문제는 스스로 해결을 못해서 다른분의 코드를 사용했다.