[프로그래머스] Level2 - 후보키(Javascript)

프로그래머스

 

📝 문제 요약

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

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

3️⃣ 유일성, 최소성을 만족시키는 후보 키의 최대 개수를 구하라.

 

 

✅ 정답 코드

function solution(relation) {
    const numRows = relation.length;
    const numCols = relation[0].length;
    // 후보키 담을 배열
    let candidates = [];
    
    // 2의 4제곱 = 16 -> (1 ~ 15) 가능한 모든 조합을 다 구한다. 비트마스킹 활용
    for (let i = 1; i < (1 << numCols); i++) {
        // 중복제거를 위해서 Set()dmf 사용
        let tempSet = new Set();
        
        
        for (let j = 0; j < numRows; j++) {
            // 열이 끝날때마다 key를 reset
            let tempKey = "";
            for (let k = 0; k < numCols; k++) {
                // 해당 속성이 선택되었는지 확인한다. 
                if ((i & (1 << k)) !== 0) {
                    // ["ryan", "music"]이 선택된 조합이라면 ryan, music같은 형태의 키를 생성한다. 
                    tempKey += relation[j][k] + ",";
                } 
            }
            // 선택된 속성으로 만든 키를 Set에 추가
            tempSet.add(tempKey);
        }

        // Set은 중복 값을 포함하지 않기 때문에 키의 개수와 행의 개수가 같으면 모든 키가 유일하다.
        if (tempSet.size === numRows) {
            let isMinimal = true;
            for (let cand of candidates) {
                // 현재의 조합 i와 이전에 확인한 후보키 조합들을 비교하여 최소성 비교
                // 만약 현재 조합 i가 이전의 후보키 조합을 포함하고 있다면, 현재 조합은 최소성을 만족시키지 않는다.
                if ((cand & i) === cand) {
                    isMinimal = false;
                    break;   
                }
            }
            // 유일성과 최소성을 만족하는 경우 배열에 추가
            if (isMinimal) {
                candidates.push(i);
            }
        }
    }
    return candidates.length;
    
}

 

📚 중요 포인트

👉 처음에 행의 속성만큼 2의 행의 속성한 이유는 모든 가능한 조합을 만들기 위해서다. 아래처럼 모든 속성이 선택되기 위해서 사용했다.

0000 -> 아무 속성도 선택되지 않음
0001 -> 첫 번째 속성만 선택됨
0010 -> 두 번째 속성만 선택됨
0011 -> 첫 번째 및 두 번째 속성이 선택됨
0100 -> 세 번째 속성만 선택됨
...
1111 -> 모든 속성이 선택됨

 

 

📔느낀점

👉 역시 카카오 기출문제라서 그런지 Level2이어도 어렵다.

👉 모든 조합을 찾을 때 비트마스킹 알고리즘을 활용하면 시간도 매우 빠르다는 것을 알게 됐다. 앞으로 조합 문제에는 적극적으로 비트마스킹을 써볼 예정이다.