[프로그래머스] 후보키 (JavaScript)

문제

프로그래머스 2019 KAKAO BLIND RECRUITMENT 후보키

 

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

코딩테스트 연습 - 후보키

언어

자바스크립트(JavaScript)

 

접근 방법

1. 테이블 컬럼의 개수 N을 이용해서 N에서 생성할 수 있는 모든 조합 리스트를 생성한다. 조합에서 값은 컬럼의 인덱스이며 각 조합에 대응되는 컬럼을 뽑았을 때 후보키가 될지 테스트하면 된다.
2. 키의 최소성을 체크한다. 키가 후보키로 등록된 키의 모든 요소를 포함하는 경우를 찾고 그 경우가 하나라도 있다면 후보에서 탈락시킨다.
3. 키의 유일성을 체크한다. 테이블의 모든 요소에서 키에 해당하는 값만 뽑아 데이터를 만들 때 하나라도 중복되는 요소가 있으면 후보에서 탈락시킨다.
4. 모두 만족하면 후보키로 등록한다.

 

코드

function solution(relation) {
    let answer = 0;
    let attrNum = relation[0].length;
    let combList = [];
    let keyList = [];
    // 조합 배열 생성
    for (let i=1; i<=attrNum; i++){
        comb(combList, [], 0, attrNum, i, 0);
    }
    // 각 조합에 따라 후보 키가 가능한지 체크하고 추가
    for (let i=0; i<combList.length; i++){
        addKey(keyList, combList[i],relation);
    }
    console.log(keyList);
    return keyList.length;
}
function addKey(keyList, key, relation){
    // 최소성 체크
    // 이미 등록된 후보키의 배열을 포함하는 배열이 하나라도 존재하면 최소성 X
    let isMin = true;
    for (let i=0; i<keyList.length; i++){
        let prevKey = keyList[i];
        for (let j=0; j<key.length; j++){
            prevKey = prevKey.filter(ele=> ele !==key[j]);
        }
        if(prevKey.length === 0){
            isMin = false;
        }
    }
    // 등록한 후보키가 하나도 없으면 최소성이 항상 만족되므로 패스
    if (keyList.length !==0 && !isMin){
        return;
    }
    let arr = [];
    let isUnique = true;
    // 유일성 체크
    // 키로 사용했을 때 하나라도 중복되면 유일성 X
    for (let i=0; i< relation.length; i++){                
        let findEle = arr.find(ele => {
            let flag = true;
            for (let j=0; j< key.length; j++){
                if (ele[key[j]] !== relation[i][key[j]])
                    flag = false;
            }
            return flag;
        })
        if (findEle !== undefined){
            isUnique = false;
        }else{
            arr.push(relation[i]);
        }
    }
    // 유일성 만족하면 후보키로 등록
    if(isUnique){
        keyList.push(key);
    }
   
}
// 조합 배열 생성
function comb(list, arr, idx, n, r, target){
    if (r===0){
        list.push(Object.assign([], arr));
    }else if (target === n){
        return ;
    }else{
        arr[idx] = target;
        comb(list, arr, idx + 1, n, r - 1, target + 1);
        comb(list, arr, idx, n, r, target + 1);
    }
}

 

복기

1. 조합 코드를 기계적으로 짤 수 있었으면 더 빨리 풀었을 듯하다. 조합 코드가 생각이 잘 안 나서 조합 안 쓰고 푸는 방법이 있을까 고민했는데, 그때 시간이 좀 흘렀다.
2. 최소성 체크 코드를 짜기가 어려웠다. 여기에 시간을 너무 많이 썼다. 반복문이 많아지면서 인덱스도 많아져 코드 짜기가 헷갈린다. 처음에 filter를 안쓰고 for 문으로 해결하다가 코드가 복잡해서 시간이 오래 걸렸고 결국 filter로 수정했다.