Level2️⃣ - 후보키(2019 KAKAO BLIND RECRUITMENT)

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

프로그래머스

 

문제 접근

입력값의 최대범위가 작기 때문에 조합을 활용한 완전탐색을 사용해도 되겠다고 판단했다.

학번	이름	과목	학년
100	ryan	music	2
200	apeach	math	2
300	tube	computer	3

 

학번, 이름, 과목, 학년과 같이 릴레이션의 속성을 조합을 활용해서 키를 구한다. 이때 후보키 리스트에서 최소성을 위배하는 키라면 제외한다. 만약 최소성을 위배하지 않았다면 유일성을 체크해야한다. 해당 키로 튜플을 유일하게 식별할 수 있는지 확인하고 만족한다면 후보키 리스트에 넣어준다.

 

오답 코드

function solution(relation) {
    // 1. 후보키 조합
    const keys = [];
    const n = relation.length;
    const m = relation[0].length;
    for(let i = 1; i<=m; i++){
        solve(i);
    }
    return keys.length;
    
    function solve(i){
        function combi(start, b){
            if(b.length === i){
                let checked = new Set();
                let str = b.join("");
                for(const k of keys){
                    if(str.includes(k)) return; // 최소성을 만족하는지 체크
                }
                for(let i = 0; i<n; i++){
                    let tmp = "";
                    for(let j = 0; j<b.length; j++){
                        tmp += relation[i][b[j]];
                    }
                    checked.add(tmp);
                }
                if(checked.size === n) keys.push(str); // 유일성을 만족하는지 체크
                return;
            }
            else {
                for(let i = start+1; i<m; i++){
                    b.push(i);
                    combi(i, b);
                    b.pop();
                }
            }
        }
        combi(-1, []);
    }
}

 

위 코드에서 일부 테스트케이스에 오류가 나왔다. 오류가 발생한 부분은 최소성을 판단하는 부분이었다.

예를 들어 후보키 리스트에 "02" 라는 후보키가 있다고 생각하자. 그리고 "023"과 "012"가 후보키를 만족하는지 체크해야한다.

위의 코드를 적용하면 "023"은 이미 "02"라는 후보키가 있기 때문에 최소성을 위배해 걸러지지만 "012"는 거르지 못한다. 하지만 "012"도 최소성을 위배하는 키이기 때문에 걸러야한다. 만약 "03"이라는 키도 판단해야한다면 "03"은 최소성을 위배하지 않는 키이다. 0과 3중 하나라도 제외하면 유일성이 깨지기 때문이다.

 

따라서 로직을 변경해야한다. 후보키 각각의 문자의 갯수를 저장해서 문자가 일치할 때마다 갯수를 차감한다. 최종적으로 0이 된다면 해당 키는 최소성을 위배하는 것이고 그렇지 않으면 만족하는 것이다.

 

어떤 경우에 조건을 만족하지 않는지 여러 케이스를 고려해야한다. 물론 쉽게 생각나지는 않지만...😢

정답 코드

function solution(relation) {
    // 1. 후보키 조합
    const keys = [];
    const n = relation.length;
    const m = relation[0].length;
    for(let pick = 1; pick<=m; pick++){
        solve(pick);
    }
    return keys.length;
    
    function solve(i){
        function combi(start, b){
            if(b.length === i){
                let checked = new Set();
                let str = b.join("");
                for(const k of keys){
                    let cnt = k.length;
                    // ✅수정한 부분
                    for(const char of k){
                        if(str.includes(char)) cnt -= 1;
                    }
                    if(cnt === 0) return; // 최소성을 만족하는지 체크
                }
                for(let i = 0; i<n; i++){
                    let tmp = "";
                    for(let j = 0; j<b.length; j++){
                        tmp += relation[i][b[j]];
                    }
                    checked.add(tmp);
                }
                if(checked.size === n) keys.push(str); // 유일성을 만족하는지 체크
                return;
            }
            else {
                for(let i = start+1; i<m; i++){
                    b.push(i);
                    combi(i, b);
                    b.pop();
                }
            }
        }
        combi(-1, []);
    }
}