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

* 2021-04-13 다시 푼 풀이

 

function solution(relation) {
    var answer = 0;
    let rlen=relation.length;
    let clen=relation[0].length;
    const subset=[];
    const set=new Set();//인덱스 조합 
    function comb(cnt,max,start){
        if(cnt===max){
            // 최소성 확인 (인덱스 중복 검사)
            let minimum=true;
            let sarr=Array.from(set);
            for(let i=0;i<sarr.length;i++){
                let isContain=true;
                for(let j=0;j<sarr[i].length;j++){
                    if(subset.indexOf(sarr[i][j])===-1){
                        isContain=false;
                        break;
                    }
                }
                if(isContain){
                    minimum=false;
                    break;
                }
            }
            if(minimum){//유일성 확인
                const dict={};
                let isOnly=true;
                for(let i=0;i<rlen;i++){
                    let temp=relation[i].filter((item,idx)=>{
                        return subset.indexOf(idx)!==-1;
                    }).join(",");
                    if(dict[temp]===undefined){
                        dict[temp]=1;
                    }else{//유일하지 않음
                        isOnly=false;
                        break;
                    }
                }
                if(isOnly){
                    set.add([...subset]);
                }
            }
            
            return;
        }
        
        for(let i=start;i<clen;i++){
            subset.push(i);
            comb(cnt+1,max,i+1);
            subset.pop();
        }
    }
    
    for(let i=1;i<=clen;i++){
        comb(0,i,0);
    }
    
    return set.size;
}

 

---

 

 

어려운 조합문제.. 이게 레벨 2라니 ㅠㅠㅠ 

일단 자바스크립트라 객체 (배열) 조심해서 풀어야된다. (set이나 map에 넣을 때도 ...arr로 복사해서 넣어야된다.)

 

조합으로 모든 길이의 경우의 수를 구해서 현재 만든 조합이 만약 이전에 넣은 배열을 포함하고 있다면 넘어가고

아닌 경우 answer+1과 result배열 (조합을 모아놓은 배열)에 추가해준다. 

 

function solution(relation) {
    var answer = 0; // 후보키 개수 
    const result=[]; //모든 포함되지 않는 조합을 담는 배열, result.length가 답일 것이다.
//     arr은 인덱스가 들어가는 위치
    function comb(arr,len,start){ // 모든 조합 구하기. (arr은 인덱스담는 배열,구하는 길이, 시작지점)   
        if(arr.length===len){ //원하는 길이의 조합이 완성되면
            const set=new Set(); //유일 키가 될 수 있는가
            let possible=true;// 겹치는 애가 없다!
            for(let i=0;i<relation.length;i+=1){ //모든 행을 돌면서 중복되는 값을 찾는다.
                const row=relation[i].filter((item,idx)=>{
                    return arr.indexOf(idx)!==-1; //조합에 담긴 위치에 있는 애들만 리턴해서
                }).join(","); //","로 조합해준다. 그 이유는 a,aa와 a,aa는 달라야된다.
                if(set.has(row)){ //만약 같은 값이 한 열에 존재한다면 
                    possible=false; //유일키 불가
                    break;
                }else{
                    set.add(row); //한 열의 모든 값이 다르다면 유일한 키이다.
                }
            }
            if(possible){//유일 키 가능, 최소키 확인하자(?!)
                let minimum=true;//일단 가능하다고 쳐!
                for(let v of result){ //조합 배열  중에서 찾아보자
                    let isContain=true; //포함되어 있는가 여부
                    for(let i=0;i<v.length;i+=1){ //각각의 키 검사 (포함 여부)
                        if(arr.indexOf(v[i])===-1){
                            isContain=false; //한 원소라도 다르다면 포함관계아님(즉, 현재 조합이 최소키이다)
                            break;//없는 것이면 다음 키 검사
                        }
                    }
                    if(isContain){ //하나라도 포함되어 있는 관계라면 최소키가 아니다.
                        minimum=false;
                        break;
                    }
                }

                if(minimum){//최소키인 것까지 맞다면 결과 배열에 추가해준다.
                    result.push([...arr]); //자바스크립트에서 객체 조심! 복사해서 넘겨준다.
                    answer+=1;
                }
                    
            }   
            return;
        }
        
        for(let i=start;i<relation[0].length;i+=1){
            // arr.push(i);
            // 조합의 위치값을 추가해주고, 그 다음 시작할 위치를 넘겨준다.
            comb([...arr,i],len,i+1); //여기서 이미 복사해서 넘겨줘서 위에서 안해도 되긴하다.
            // arr.pop();
        }
    }
    //1개~열의 길이의 조합을 만들 수 있다. (후보키의 조합)
    for(let i=1;i<=relation[0].length;i+=1){
        comb([],i,0);
    }
    
    return answer;
}