[Programmers] (2019 KAKAO BLIND RECRUITMENT) Lv 2. 후보키

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

프로그래머스

 

// 조합
const getCombination = (elements, pick) => {
    if (pick === 1) return elements.map((elem) => [elem]);

    const combinations = [];
    elements.forEach((element, index) => {
        const smallerCombinations = getCombination(elements.slice(index + 1), pick - 1);

        smallerCombinations.forEach((combination) => combinations.push([element].concat(combination)));
    });

    return combinations;
};

// 유일성 체크
const uniqueness = (relation, elements, row) => {
    const arr = new Array(row).fill("");
    elements.forEach((attr) => {
        for (let tuple = 0; tuple < row; ++tuple)
            arr[tuple] += relation[tuple][attr];
    });

    return !arr.some((x) => arr.indexOf(x) !== arr.lastIndexOf(x)); // 중복체크
};

// 최소성 체크
const minimality = (answer, elements) => {
    return answer.length
        ? answer.every((arr) => arr.filter((a) => elements.some((b) => a === b)).length !== arr.length)
        : true;
};

function solution(relation) {
    const answer = [];
    const [attribute, row, column] = [Array.from({ length: relation[0].length }, (_, idx) => idx), relation.length, relation[0].length];

    for (let i = 1; i <= column; ++i) {
        const combinations = getCombination(attribute, i); // '조합'으로 경우의 수를 만든다.
        combinations.forEach((elements) => {
            if (uniqueness(relation, elements, row) && minimality(answer, elements)) // 유일성 & 최소성 체크
                answer.push(elements);
        });
    }

    return answer.length;
}

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/42890.%E2%80%85%ED%9B%84%EB%B3%B4%ED%82%A4

GitHub - developeSHG/Algorithm-Baekjoon_Programmers: 백준 and 프로그래머스 소스코드