[프로그래머스][dfs] 후보키

     

목차

 

문제

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

프로그래머스

 

 

문제 구현 방향

모든 문자열에 대한 조합을 구한 뒤 조건을 만족하는지에 대한 검사를 한 후 후보에 추가하는 식으로 코드를 작성했다.

 

 

 

가져갈 부분

최소성을 체크할 때 배열에 부분적으로 그 배열이 있는 지 확인하는 로직은 가져가면 좋을 것 같다.

 ex) dic = [[1, 2]]  arr = [1, 2, 3] -> true

  function minCheck(dic, arr) {
        let isMinimal = true;
        for (let key of dic) {
            if (key.every((k) => arr.includes(k))) {
                isMinimal = false;
                break;
            }
        }
        return isMinimal;
    }

 

 

코드 구현

function solution(relation) {
    var answer = 0;
    let arr = [];
    let dic = [];
    let rowLen = relation.length;
    let colLen = relation[0].length;

    function minCheck(dic, arr) {
        let isMinimal = true;
        for (let key of dic) {
            if (key.every((k) => arr.includes(k))) {
                isMinimal = false;
                break;
            }
        }
        return isMinimal;
    }

    function uniqueCheck() {
        let s = new Set();

        for (let i = 0; i < rowLen; i++) {
            let str = "";
            for (let idx of arr) {
                str += `-${relation[i][idx]}`;
            }
            s.add(str);
        }
        
        if (s.size === rowLen) return true;
        return false;
    }

    function combi(idx, arr, n) {
        if (arr.length === n) {
            let isMinimal = true;

            if (!minCheck(dic, arr)) return;

            if (!uniqueCheck()) return;
            
            dic.push([...arr]);

            return;
        }
        for (let i = idx; i < colLen; i++) {
            arr.push(i);
            combi(i + 1, arr, n);
            arr.pop();
        }
    }
    for (let i = 1; i <= colLen; i++) {
        combi(0, arr, i);
    }
    return dic.length;
}