[프로그래머스] 코딩테스트 연습 - 69

level 2 - 후보키

관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.

• 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
• 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

입출력 예시
relation : [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]
-> 2

function solution(relation) {
    var answer = [];
    var result = [];
    var cnt = 0;
    var col = relation[0].length;
    
    dfs(0, '');
    function dfs(idx, str) {
        if (str) {
            var cnt = 0;
            var arr = str.split("").map((a) => Number(a));
            var tmp = relation.map((rel) => rel.filter((_, i) => arr.includes(i))).map((rel) => rel.join(""));
            if (new Set(tmp).size == relation.length) {
                answer.push(arr);
                return;
            }
        }
        for(var i=idx; i<col; i++){
            dfs(i + 1, str + i);
            dfs(i + 1, str);
        }
        return;
    }
    
    answer = [...new Set(answer.sort((a, b) => a.length - b.length).map((ans) => ans.join("")))];
    answer.forEach((ans) => {
        var arr = ans.split("");
        var is_min = true;
        for(var i=0; i<result.length; i++) {
            var visited = 0;
            for(var j=0; j<arr.length; j++) {
                if (result[i].includes(arr[j])) visited++;
            }
            if(visited == result[i].length) {
                is_min = false;
                break;
            }
        }
        if (is_min) {
            result.push(ans)
            cnt++;
        }
     })
    return cnt;
}

쉽게봤는데 자꾸 찔끔찔끔 틀리더라
허허

허허허허ㅓ

오래걸림😢