문제 접근

문제는 간단하다. 그냥 유일성과 최소성을 만족하는 모든 후보키를 구하면 된다. 컬럼의 최대 개수는 8개, 튜플의 최대개수는 20개로 그냥 구현문제다.
다만, 여기서 최근에 사용하고 싶었지만 적당한 문제를 못찾아 적용을 못하고 있던 비트마스킹을 사용할 기회를 봤다.

속성이 최대 8개이므로, 속성의 집합은 비트마스킹으로 0~255 숫자로 표현이 가능하다.
내가 해결한 방법은 다음과 같다.

• 우선, 속성의 집합 크기 별로(반드시 작은 집합부터 구할것) 조합을 모두 구한다.
• 구한 집합이 유일성과 최소성을 만족하면 checked배열에 해당 집합 인덱스값으로 true를 설정해준다.

유일성 판단 로직

릴레이션을 돌면서, 집합에 속한 속성이면 StringBuilder를 통해 차곡차곡 해당 컬럼의 값을 뒤에 추가한다.
이렇게 만든 String배열을 사전순으로 정렬한다.
정렬한 상태에서 만약 이웃에 같은 스트링이 존재한다면 이는 유일성을 만족하지 못하는 것이다.

최소성 판단 로직

위에서 나는 속성의 집합을 작은 집합부터 구해서 체킹을 했다.
만약 이미 유일성과 최소성을 만족해서 후보키로 등재된 00010001 (십진수로 17) 이 있다고 가정하자.
이번에 최소성을 만족하는지가 궁금한 00110101 (십진수로 53) 이 있다면, 기존의 checked배열을 돌면서 이미 후보키로 등재된 모든 집합들과 00110101 을 비교를 할것이다. 이때, 00010001 & 00110101 은 00010001 이다. 즉, 이미 후보키로 등재된 속성들을 그대로 00110101 이 포함하고 있다는 의미이므로 후보키가 될 수 없다.

문제 풀이

import java.util.*;

class Solution {
    int columnSize;
    int rowSize;
    boolean[] checked;
    int setSize;
    public int solution(String[][] relation) {
        int answer = 0;
        columnSize = relation[0].length;
        rowSize = relation.length;
        setSize = 1<<columnSize;
        checked = new boolean[setSize];
        
        for(int i=1; i<=columnSize; i++) {
            ArrayList<Integer> setBits = new ArrayList();
            findSets(setBits, i, 0, 0, 0);
            for(int j=0; j<setBits.size(); j++) {
                int curSet = setBits.get(j);
                if ( isMinimum(curSet) && isUnique(relation,curSet) ) {
                    answer++;
                    checked[curSet] = true;
                }
            }
        }
        
        return answer;
    }
    
    boolean isUnique(String[][] relation, int setBit) {
        String[] arrays = new String[rowSize];
        for(int i=0; i<rowSize; i++) {
            StringBuilder sb = new StringBuilder();
            int j = columnSize-1;
            for(int b=1; b<setSize; b*=2, j--) {
                if ((setBit & b) != 0) {
                    sb.append(relation[i][j]);
                }
            }
            arrays[i] = sb.toString();
        }
        
        Arrays.sort(arrays);
        
        for(int i=0; i<rowSize-1; i++) {
            if (arrays[i].equals(arrays[i+1])) return false;
        }
        return true;
    }
    
    boolean isMinimum(int setBit) {
        for(int i=0; i<setSize; i++) {
            if (checked[i] && ((i&setBit) == i)) {
                return false;
            }
        }
        return true;
    }
    
    void findSets(ArrayList<Integer> result, int size, int sIndex, int count, int value) {
        if (count == size) {
            result.add(value);
            return;
        }
        
        for(int i=sIndex; i<columnSize; i++) {
            findSets(result, size, i+1, count+1, value + (1<<i));
        }
    }
}