[programmers] 후보키

14 Apr 2023 in Algorithm on Algorithm

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

문제를 잘 보면 N 개의 컬럼을 조합하여 얻을 수 있는 키의 갯수를 구하는 문제 이다.
즉, 조합 문제로 우선 조합의 갯수를 구해보자

컬럼이 n개 있을 때, 각 컬럼은 선택하거나 안 할 수 있다.
즉, 각 컬럼은 2가지 선택지:

포함할까? (1)
포함하지 않을까? (0)

이게 n개 있으니까 가능한 조합 수 = 2 × 2 × 2 × … (n번) = 2^n
여기에 공집합(아무것도 포함하지 않은 조합)은 빼줘야 하니 2^n-1이 된다.

4개의 컬럼일 경우 1 ~ 15 까지의 조합의 수가 나오는데 2진수로 표현할 경우 각자리에 1이 올때 해당 값이 포함되는 조합이 된다.
이걸이용해 비트 연산을해 최소성을 확인할 수 있다.

int key = 0110;   // 10
int set = 1110;   // 14
(key & set) = 0110

// 결과(key는 set의 부분집합이니까 → 이건 후보키가 될 수 없음 (최소성 위반))
(key & set) == key // true

import java.util.*;

class Solution {
    int rowSize, colSize;
    List<Integer> candidateKeys = new ArrayList<>();

    public int solution(String[][] relation) {
        rowSize = relation.length;
        colSize = relation[0].length;

        // 비트마스킹으로 모든 조합 확인 (1부터 2^colSize - 1까지)
        for (int set = 1; set < (1 << colSize); set++) {
            if (!isMinimal(set)) continue;
            if (isUnique(set, relation)) {
                candidateKeys.add(set);
            }
        }

        return candidateKeys.size();
    }

    // 유일성 체크
    private boolean isUnique(int set, String[][] relation) {
        Set<String> seen = new HashSet<>();

        for (int i = 0; i < rowSize; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < colSize; j++) {
                if ((set & (1 << j)) != 0) {
                    sb.append(relation[i][j]).append(",");
                }
            }
            if (!seen.add(sb.toString())) return false; // 중복 발생
        }

        return true;
    }

    // 최소성 체크
    private boolean isMinimal(int set) {
        for (int key : candidateKeys) {
            if ((key & set) == key) return false; // 이미 있는 후보키의 부분집합
        }
        return true;
    }
}