[프로그래머스 레벨투] 후보키 🗝

🔽 문제 링크

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

✍🏼 나의 수도 코드

  1) 우선 각 컬럼의 조합을 만든다.
  2) 해당 조합들을 하나씩 검토하며, 튜플이 고유한지 판별한다.
  3) 튜플이 고유할 경우 해당 조합을 포함하는 조합은 모두 목록에서 삭제한다.

👨🏻‍💻 나의 문제 풀이

const getCombinations = function(arr, selectNumber) { 
  const results = [];

  if(selectNumber === 1) return arr.map((value) => [value]); 
  
  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest, selectNumber - 1);
    const attached = combinations.map((combination) => [fixed, ...combination]);
    results.push(...attached);
  })
  
  return results;
}

function solution(relation) {
    let result = 0;
    
    let colNum = relation[0].length;
    let initArr = new Array(colNum).fill(0).map((_, i) => i);
    let candidateKeyArr = [];
    for(let i = 1; i <= colNum; i++){
        candidateKeyArr = candidateKeyArr.concat(getCombinations(initArr, i))
    }
    candidateKeyArr = candidateKeyArr.map(arr => arr.join(""))
    
    for(let i = 0; i < candidateKeyArr.length; i++){
        let choosenKeys = candidateKeyArr[i].split("").map(el => Number(el));
        let filteredRelation = relation.map(arr => {
            return arr.filter((_, i) => choosenKeys.includes(i)).join("");
        })
        if(filteredRelation.every((str, i) => filteredRelation.indexOf(str) === i)){
            result++;
            candidateKeyArr = candidateKeyArr.filter(str => !choosenKeys.every(key => str.includes(key)) || str.length === candidateKeyArr[i].length);
        }
    }
    return result;
}

👩🏻‍💻 다른 사람의 코드

function solution(relation) {
    const cols = relation[0].length;

    const check = 1 << cols;
    const answer = new Set();

    for(let i = 1; i < check; i++){
        let temp = relation.map(x=>x.filter((col,index)=>i & (1<<index)).join(""));
        const set  = new Set(temp);

        if(temp.length === set.size) answer.add(i);
    }

    for( let x of answer){
        for ( let y of answer){
            if(x >= y) continue;
            if((x & y) === x) answer.delete(y);
        }
    }
    return answer.size;
}

🍯 알게 된 것들

• 똑같은 요소 있는지 판별할 때, filter와 인덱스 조합으로도 가능하지만, Set을 활용해도 된다.
• <<, & 비트연산자