[프로그래머스][LEVEL2] 후보키

# 문제 원문

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보 키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보 키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

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

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

relation / result

[["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

 

# 문제 풀이

엄청 헤매고 어려웠던 문제이다. 실제로 코테에서 나왔으면 지금 수준에서는 못 풀었을 거 같다. 비트 마스크에 대해서 잘 알면 쉽게 풀 문제이기도 하다. 난 잘 몰라서 어려웠다. 단순 무식하게 DFS로 모든 조합을 구해서 필터링하고 카운팅 했다. 입력받은 relation 튜플의 각 칼럼의 조합이 최소 조합으로 유니크할 수 있는 조합을 모두 찾아서 그 개수를 반환하는 문제이다. 개인적으로 풀고 나니 그 외에도 쓸데없는 부분이나 이상하게 돌아간 부분이 많아서 아쉽다. 나중에 다시 풀어봐야겠다.

 

# 솔루션 플로우

1. 입력 받은 relation(튜플 배열)의 각 col를 묶어서 2차원 배열 cols로 만든다. (각 col 첫 번째 요소에 '#순서'삽입)

2. DFS 알고리즘을 이용해서 cols의 모든 조합 중 유일한 조합을 얻는다.

3. 유일한 조합 cols를 모두 순회하면서 유일하고 최소한 후보키들을 얻어서 그 개수를 count 한다.

4. 얻어진 result를 반환한다.

1. DFS를 활용한 풀이

function solution(relation) {
    let cols = relation.reduce((result, row) => {
        row.forEach((col, idx) => result[idx].push(col));
        return result;
    }, new Array(relation[0].length).fill(true).map((_, idx) => [`#${idx}`]));
    cols = comb(cols);

    let result = 0;
    while (cols.length > 0) {
        result++;
        cols = cols.filter((col) => !cols[0].every((key) => col.includes(key)));
    }

    return result;

    function comb(cols) {
        const result = new Set();
        const pre = [];

        cols.forEach((_, idx) => dfs(Array.from(cols), idx + 1));

        return Array.from(result);

        function dfs(cols, n) {
            if (pre.length === n) {
                let check = true;
                Array.from(pre).reduce((result, current) => {
                    const state = Array.from(result);
                    current.forEach((current, idx) => state[idx] += ':' + current);
                    return state;
                }).forEach((current, idx, arr) => {
                    if (arr.indexOf(current) !== idx) {
                        check = false;
                    }
                });
                if (check) {
                    result.add([...pre.map((col) => col[0])]);
                }
            } else {
                for (let int = 0; int < cols.length; int++) {
                    pre.push(cols[int]);
                    dfs(cols.slice(int + 1), n);
                    pre.pop();
                }
            }
        }
    }
}