[프로그래머스] 후보키(2019 KAKAO BLIND RECRUITMENT) - JavaScript

 

 

이전에 Java로 풀었던 후보키 문제를 JavaScript로 다시 풀어봤습니다.

 

 

아이디어 자체는 같으나 언어에 따라 사용하는 자료구조나 메소드에 조금씩 차이가 있기 때문에 한 번 다시 풀어봤습니다.

 

const candidateSet = [];
const combSet = new Set();
function solution(relation) {
    let answer = 0;
    
    for(let i = 1; i<1<<relation[0].length; i++){ // 비트마스크를 이용한 조합 생성
        if(!checkCandidate(i, relation)) continue; // 유일성을 만족하지 않는 경우
        if(checkSubSet(i)) continue; // 최소성을 만족하지 않는 경우
        candidateSet.push(i);
    }
    answer = candidateSet.length;
    return answer;
}

const checkCandidate = (key, relation) => {
    const checkSet = new Set();
    for(let i = 0; i<relation.length; i++){
        let keyStr = "";
        for(let j=0; j<relation[0].length; j++){
            if(key&1<<j) keyStr+=relation[i][j]; // 비트마스크를 이용해 해당하는 키 값 가져오기
        }
        if(checkSet.has(keyStr)) {
            return false;
        }
        checkSet.add(keyStr);
    }
    return true;
}

const checkSubSet = (key) => {
    for(let candidate of candidateSet){
        if((key&candidate)===candidate) return true; // 비트마스크를 이용한 부분집합 판단
    }
    return false;
}

 

* 조합 구할 때 성능을 위해 비트 마스크 이용하기(재귀 X)

 

 

이전 글

2021/01/09 - [Algorithm] - [프로그래머스] 후보키(2019 KAKAO BLIND RECRUITMENT)

[프로그래머스] 후보키(2019 KAKAO BLIND RECRUITMENT)