[프로그래머스 Level 2] 후보키 - JavaScript

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(relation) {
    const rowLen = relation.length;
    const colLen = relation[0].length;
    let answer = 0;
    
    const bfs = () => {
        const queue = [...Array(colLen)].map((_, i) => [i]);
        const candidate = [];
        while (queue.length) {
            const indices = queue.shift();
            
            // 최소성을 만족하지 않는 경우 제외
            if (candidate.find(cand => cand.every(index => indices.includes(index)))) {
                continue;
            }
            
            const set = new Set();
            for (let i = 0; i < rowLen; i++) {
                set.add(JSON.stringify(indices.map((index) => relation[i][index])));
            }
            
            // 유일성을 만족하면 candidate에 추가
            if (set.size === rowLen) {
                candidate.push(indices);
            
            // 유일성을 만족하지 않으면 컬럼을 하나 더 추가
            } else {
                 for (let i = indices[indices.length - 1] + 1; i < colLen; i++) {
                    queue.push([...indices, i]);
                }
            }
        }
        
        return candidate.length;
    };
    
    return bfs();
}

처음에 후보 키를 컬럼 1개만으로 유일성을 만족하는지 따져본다.

유일성을 만족한다면 앞으로 그 컬럼은 다른 후보 키에 포함되어서는 안 된다.

유일성을 만족하지 않는다면 다른 컬럼을 하나 더 포함해서 유일성을 만족하는지 다시 따져본다.

 

유일성을 만족할 때마다 candidate 배열에 후보 키를 추가하는데,

queue를 순회할 때마다 이 candidate 배열과의 비교를 통해 최소성을 만족하는지도 같이 따져본다.

 

위 과정을 반복하면 candidate 배열에 후보 키(후보 키에 포함되는 컬럼의 인덱스 배열)들이 담기게 되고, 최종적으로 그 길이를 반환하면 정답이다.