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

문제

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

주어진 데이터를 구분할 수 있는 후보키가 몇개인지 구하는 문제이다.

해결방법

1. 후보키로 사용할 Attribute 인덱스의 모든 부분집합을 구한다.
2. 인덱스 집합의 길이(배열의길이)가 작은 순으로 후보키 검사를한다.
   2-1. 후보키로 가능할 경우 : 인덱스 집합의 들은 요소를 모두 포함한 부분집합을 제거한다.
   2-2. 후보키로 가능하지 않는 경우: 방금 검사한 인덱스 집합을 제거한다.

전체적인 로직은 위와 같이 간단하다. 하지만 이를 구현하기 위해서는 아래의 두가지 함수구현이 필요하다.

• 모든 부분집합(멱집합) 구하는 함수
• 후보키인지 판별해주는 함수

powerSet. 멱집합 구하는함수

멱집합을 구하는 법은 멱집합 구하기 포스팅에서 소개했다.
단, 이 문제에서는 2개의 filter가 필요하다.
1. 멱집합에는 공집합 즉, 빈배열 []을 제거해준다.
2. 후보키 조건 중 최소성이 있기 때문에 배열의 길이가 작은 것부터 판별해줘야 되기 때문에 정렬을 해줘야한다.

checkOverlap. 후보키 판별 함수

후보키로 들어오는 속성들을 문자열로 바꿔서 setArr에 넣는다. (setArr.add(문자열))

후보키는 유일성 속성에 의해 중복이 일어나면 안된다.
setArr에 후보키들을 문자열로 연결한 값이 있다면(setArr.has(문자열)) 중복이 있다는 뜻이기 때문에 false를 반환한다.

checkOverlap이 true일 경우

checkOverlap(부분집합)이 true일 경우 현재 부분집합을 포함하고 있는 모든 부분집합을 제거해줘야한다. (최소성 때문)
filter를 이용해 checkOverlap에서 true를 반환한 부분집합을 포함하는 부분집합은 모두 제거해준다.

//caseIndexArr: 모든 부분집합을 갖고있는 배열
//nowCase : 후보키 검사를 한 부분집합 
 caseIndexArr = caseIndexArr.filter((idxArr) => {
        //지금 nowCase의 인덱스를 모두 포함하고있는 caseIndexArr의 요소를 제외
        for (let idx of nowCase) {
          if (!idxArr.includes(idx)) return true;
        }
        return false;
      });

code

function solution(relation) {
  let answer = 0;
  //Attribute의 인덱스 배열
  const indexArr = Array.from({ length: relation[0].length }, (_, idx) => idx);

  //Attribute의 인덱스배열의 모든 부분집합을 구한다.
  let caseIndexArr = powerSet(indexArr);

  while (caseIndexArr.length) {
    const nowCase = caseIndexArr[0];
    //nowCase에 있는 index의 Attribute로만 배열을 만든다.
    const checkRelation = relation.map((v) =>
      v.filter((_, idx) => nowCase.includes(idx))
    );

    //후보키 체크
    if (checkOverlap(checkRelation)) {
      answer++;
      caseIndexArr = caseIndexArr.filter((idxArr) => {
        //지금 nowCase의 인덱스를 모두 포함하고있는 caseIndexArr의 요소를 제외
        for (let idx of nowCase) {
          if (!idxArr.includes(idx)) return true;
        }
        return false;
      });
    } else {
      //nowCase제거
      caseIndexArr.shift();
    }
  }

  return answer;
}

function checkOverlap(arr) {
  const setArr = new Set();
  for (let x of arr) {
    if (setArr.has(x.join(""))) return false;
    else setArr.add(x.join(""));
  }
  return true;
}
//모든 부분집합 (멱집합)
function powerSet(arr) {
  let check = new Array(arr.length).fill(0);
  let powerSetArr = [];
  const dfs = (depth) => {
    if (depth === check.length) {
      powerSetArr.push(arr.filter((_, idx) => check[idx]));
    } else {
      check[depth] = 1;
      dfs(depth + 1);
      check[depth] = 0;
      dfs(depth + 1);
    }
  };
  dfs(0);
  powerSetArr.sort((a, b) => a.length - b.length);
  powerSetArr = powerSetArr.filter((v) => v.length);
  return powerSetArr;
}

마무리

문제를 풀면서 멱집합을 구현하는 방법도 익히고 포스팅까지 하게 됐다.

문제를 해결한 후 프로그래머스에 올라온 다른 사람의 풀이를 보았다.
내가 푼 방식과 다르게 다른 사람들의 답안을 보니 <<라는 비트연산자? 도 사용했던데 아직 어떻게 해결한 것인지는 모르겠다. 내코드보다 훨씬 간결해 보이던데 공부해봐야겠다.