프로그래머스 Lv2: 후보키

https://programmers.co.kr/learn/courses/30/lessons/42890?language=javascript

풀긴 풀었는데 부분집합을 만들 때 재귀로 푼 문제. 그렇지만 다른 사람의 풀이를 보고 비트연산의 간단함과 효율성에 감탄하고 bitmask라는 개념을 이용해 부분집합을 만드는 새로운 알고리즘을 배웠고, 다시 풀어보았다.

function solution(relation) {
    let row = relation.length;
    let col = relation[0].length;
    let count = 0;
    let bitMaskList = [];
  
    // 최소성 체크 함수
    function minimalityCheck(list, set){
        let size = list.length;
        for (let i = 0; i < size; ++i){
            // 비트 & 연산은 둘다 1일 때 1이 된다.
            // set 에 이미 사용한 특성이 담겨있다면 & 연산을 할 시
            // 기존의 특성이 나온다.
            if ((list[i] & set) === list[i]) return false;
        }
        list.push(set);
        return true;
    }
  
    for (let i = 0; i < (1 << col); ++i){
        // 1. bitmask 로 가능한 모든 부분집합을 만든다.
        let keySet = new Set();
        for (let r = 0; r < row; ++r){
            // tuple 을 만든 뒤 set 에 넣는다.
            let key = '';
            for (let j = 0; j < col; ++j) {
                if (i & (1 << j)) key += relation[r][j];
            }
            keySet.add(key);
        }
        // 2. 유일성과 최소성을 체크한다.
        if (keySet.size === row // 유일성
            && minimalityCheck(bitMaskList, i)) // 최소성
            count++;
    }
    return count;
}