후보키

import java.util.*;
class Solution {
        private static ArrayList<ArrayList<Integer>> allList = new ArrayList<ArrayList<Integer>>();
    private static ArrayList<ArrayList<Integer>> key = new ArrayList<ArrayList<Integer>>();
 
    public static void makeKey(String[][] relation, int data[], boolean[] include, int k, int m, int n) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if (n == k) {
            for (int i = 0; i < n; i++) {
                if (include[i])
                    list.add(data[i]);
            }
            if (!list.isEmpty() && isUnique(relation, list, m))
                allList.add(list);
            return;
        }
        include[k] = false;
        makeKey(relation, data, include, k + 1, m, n);
        include[k] = true;
        makeKey(relation, data, include, k + 1, m, n);
    }
 
    public static boolean isUnique(String[][] relation, ArrayList<Integer> list, int m) {
        HashSet<String> tmp = new HashSet<String>();
        // 해당 조합 순서대로 hashset에 값 저장
        for (int j = 0; j < m; j++) {
            StringBuilder sb = new StringBuilder();
            for (int i : list)
                sb.append(relation[j][i]);
            tmp.add(sb.toString());
        }
        // 중복된 요소가 없는 경우 유일성을 만족함
        if (tmp.size() == m)
            return true;
        else
            return false;
    }
 
    public static boolean isMinimal(ArrayList<Integer> list) {
        ArrayList<Integer> tmp = new ArrayList<Integer>(list);
        // 요소를 하나씩 제거하여 포함되는지 확인
        for (int j = 0; j < list.size(); j++) {
            int n = tmp.remove(j);
            if (allList.contains(tmp)) {
                return false;
            }
            tmp.add(j, n);
        }
        return true;
    }
    
    public int solution(String[][] relation) {
        int m = relation.length;
        int n = relation[0].length;
        boolean[] include = new boolean[n];
        int[] data = new int[n];
        int answer;
 
        // 조합 얻기위한 배열 초기화
        for (int i = 0; i < n; i++) {
            data[i] = i;
        }
        // 유일성을 만족하는 키 조합 저장
        makeKey(relation, data, include, 0, m, n);
 
        // 최소성을 만족하는 키 조합 추출
        for (ArrayList<Integer> l : allList) {
            if (isMinimal(l))
                key.add(l);
        }
        answer = key.size();
        return answer;
    }
}

입력받은 테이블에 대해 후보키의 갯수를 구하는 문제이다.

 

해결해야 할 문제는 다음과 같다.

1. 모든 조합 구하기

2. 유일성 조건 검사

3. 최소성 조건 검사

 

모든 조합을 구하기 위해서 기존에 사용한 방법은 순서까지도 고려된 조합이었다.

하지만 이 경우에는 순서는 상관 없고, 값의 조합만 구분되어야 한다.

이를 구분한 것을 멱집합이라고 하며, 얼마전에 내용을 정리하여 게시하였다. (https://zzunsik.tistory.com/133)

 

유일성 조건을 검사하기 위해서 얻어낸 조합의 순서로 String 값을 만들어 Set에 추가한다.

튜플의 수 m만큼 Set의 size가 나오지 않을 경우, 중복된 경우가 있다는 뜻이다.

 

최소성의 경우는 내가 알고 있던 개념과 조금 달랐다.

튜플을 구분하기 위한 최소의 집합이라는 건 맞았지만, 집합의 속성이 가장 작은 값만 해당되는 것은 아니었다.

예를 들어 유일성을 만족하는 집합이 {0}, {1, 2}, {1, 2, 3}일 경우, 후보키는 {0}과 {1, 2}이다.

{1, 2, 3}은 3을 굳이 포함시키지 않아도 {1, 2}로 구분되기 때문에 최소의 집합이 아니다.

{1, 2}는 어느 요소 하나를 제거하면 바로 유일성을 잃기 때문에 최소의 집합이고, 후보키에 해당한다.

 

과정을 정리하면 다음과 같다.

1. 테이블의 컬럼 수 만큼 값을 저장하고, 컬럼의 조합에 따른 멱집합을 구한다.

2. 해당 순서로 구성된 값을 Set에 추가하고, 행의 길이와 Set의 길이가 같을 경우 유일성을 만족한다.

3. 각 요소를 제거한 조합이 키 조합에 포함되는지 확인하고, 포함되지 않을 경우 최소성을 만족한다.