[프로그래머스] 후보키 (2019 kakao blind recruitment) / javascript

접근방식

우선 인풋범위가 매~~우 작기 때문에 완탐으로 풀어도, O(N^3)으로 풀어도 차고 넘친다고 생각을 했다.

[["100","ryan","music","2"],
["200","apeach","math","2"],
["300","tube","computer","3"],
["400","con","computer","4"],
["500","muzi","music","3"],
["600","apeach","music","2"]]

그래서 이런식으로 되어있는 relation 인풋에 대해서 우선 유일성과 최소성을 고려하지 않고
나올 수 있는 모든 후보키 조합을 생각해보기로 한다.

여기서는 키의 명칭을 학번,이름,전공,학년으로 표시할 수 있었지만
우리가 문제를 풀때는 인풋에 따라서 100이 학번인지 ryan이 이름인지 알 수 없기때문에 그냥 인덱스값으로 구분하도록 하자.

Ex)

[0,1,2,3]으로 만들 수 있는 키 조합을 생각한다.

조합과 순열을 구하는 방법은 이곳에 따로 정리를 해보았다.
[0,1,2,3]에서 나올 수 있는 조합의 경우의 수는 아래와 같다.

combinations=
[
  [ 0 ],          [ 1 ],
  [ 2 ],          [ 3 ],
  [ 0, 1 ],       [ 0, 2 ],
  [ 0, 3 ],       [ 1, 2 ],
  [ 1, 3 ],       [ 2, 3 ],
  [ 0, 1, 2 ],    [ 0, 1, 3 ],
  [ 0, 2, 3 ],    [ 1, 2, 3 ],
  [ 0, 1, 2, 3 ]
]

이제 이 후보키들 중에서 유일성을 만족하고 && 최소성까지 만족하는 후보를 갱신해나가면 된다

유일성 체크

1. 위의 combinations 배열과 문제에서 정의된 relation을 함수의 인자로 받는다.
2. combinations 배열을 순회해나가며 조합 하나하나씩 유일성을 만족하는지 검사한다.
3. relation 배열에서 현재 순회중인 combinations 조합으로 후보키를 만들어서 중복을 허용하지 않는 자료구조인 set에 넣어본다.
4. 이 때, 중복이 제거된 set의 크기와 원본 relation의 길이와 같다면 다 다른것끼리 모인것이므로 유일성을 만족하는것이다.

아래 주석을 보면 좀 더 이해하기 쉽다!

function checkUniqueness(relation,combinations){
    let results = []; // 유일성을 만족하는 조합들로만 이루어진 results 배열
  
    combinations.forEach((combination) => { 
        let set = new Set(); 
        relation.forEach((rel) => {  
            set.add(combination.map(combi => rel[combi]).join(','));
            // ex) 현재 조회중인 combination을 [1,3]이라고 하면, combi는 1,3 각각 그 원소를 뜻함
            // 중첩반복문이 많아서 O(N^3)인데, 입력범위가 매~우 적어서 이정도면 효율성 매우 충분함
        });
        // 이때 만들어지는 Set은 relation 배열을 순회해나가면서 인덱스 1번째와 3번째를 합친
        // { 'ryan,2', 'apeach,2', 'tube,3', 'con,4', 'muzi,3' }의 형태임 
        // 해당 set은 relation의 길이인 6보다 작기때문에 중복이 존재했던것임. 유일성 만족 x
        if(set.size == relation.length){
            results.push(combination); 
        }
    }); 
    return results;
}

최소성 체크

문제에서는 너무 길게 설명해놓았는데,
후보키들을 순회해나가면서 이미 앞에 등록된 후보키의 배열을 포함하는 배열이 하나라도 존재하면 최소성을 만족시키지 않는다는것을 유의하면 된다.

function checkMinimality(combinations){
    let results=[]; // 최소성을 만족하는 조합들로만 이루어진 results 배열
  
    while(combinations.length){
        results.push(combinations[0]);
      	// 유일성을 만족하는 조합중 첫번째 원소를 최소성을 만족하는 원소로 넣는다. 
        combinations=combinations.reduce((acc,cur)=>{
            let notMinimal=combinations[0].every(combination=>cur.includes(combination));
            // 현재 조회중인 cur배열 안에 combinations[0]의 모든 원소가 포함된다면 최소성을 만족하지 않는것임
            if(!notMinimal) acc.push(cur); 
            // 최소성을 만족하는 cur 조합을 acc에 추가해줌
            return acc;
        },[])
        // combinations들은 combinations[0]과 비교해서 최소성을 만족하는애들로 갱신됨
    }
  
    return results;
    
}

최종 코드

function solution(relation) {
    let answer = 0;
    // relation[0]의 길이만큼 인덱스번호를 원소로 가지는 초기배열을 만든다.
    let idxArr = Array.from(Array(relation[0].length), (v, i) => i);
    
  	let combinations=[]; //가능한 후보키들의 모든 조합을 우선 넣기
  
    for(let i=0;i<idxArr.length;i++){
        combinations.push(...getCombination(idxArr,i+1))
    }
    
    combinations = checkUniqueness(relation, combinations);  //유일성 체크해서 갱신
    combinations = checkMinimality(combinations); // 최소성 체크해서 갱신
  
    return combinations.length

}


function checkUniqueness(relation,combinations){
    let results = []; 
  
    combinations.forEach((combination) => { 
        let set = new Set(); 
        relation.forEach((rel) => {  
            set.add(combination.map(combi => rel[combi]).join(','));
        });
        if(set.size == relation.length){
            results.push(combination); 
        }
    }); 
    return results;
}


function checkMinimality(combinations){
    let results=[]; 
  
    while(combinations.length){
        results.push(combinations[0]);
        combinations=combinations.reduce((acc,cur)=>{
            let notMinimal=combinations[0].every(combination=>cur.includes(combination));
            if(!notMinimal) acc.push(cur); 
            return acc;
        },[])
    }
  
    return results;
    
}



function getCombination(arr,selectNum){
    let result=[];
    if(selectNum===1){
        return arr.map(a=>[a])
    }
    arr.forEach((fix,i,origin)=>{
        const rest=origin.slice(i+1);
        const combi=getCombination(rest,selectNum-1);
        const attach=combi.map((c)=>[fix,...c]);
        result.push(...attach)
    })
    return result;
}

level2인데 어려워..ㅠㅠ....🥺