후보키

코딩테스트 연습 - 후보키

import java.util.*;

class Solution {
    boolean check(String[][] relation, int rowsize, int colsize, int subset){
        for(int a = 0; a < rowsize -1; ++a){
            for(int b = a+1; b < rowsize; ++b){
                boolean isSame = true;
                for (int k = 0 ; k < colsize; ++k){
                    if((subset & 1 << k) == 0) continue;
                    if(relation[a][k].equals(relation[b][k]) == false){
                        isSame = false;
                        break;
                    }
                }
                if(isSame) return false;
            }
        }
        return true;
    }
    Comparator<Integer> comp = new Comparator<Integer>(){
        public int compare(Integer a , Integer b){
            int x = Integer.bitCount(a);
            int y = Integer.bitCount(b);
            return x-y;
            
        }
    };
    
    public int solution(String[][] relation) {
        int answer = 0;
        int rowsize = relation.length;
        int colsize = relation[0].length;
        List<Integer> candidates = new LinkedList<Integer>();
        
        for(int i= 1; i < 1<<colsize; ++i){
            if(check(relation,rowsize, colsize, i) == true)
                candidates.add(i);
        }
        
        Collections.sort(candidates, comp);
        
        while(candidates.size() != 0){
            int n = candidates.remove(0);
            ++answer;
            
            for(Iterator<Integer> it = candidates.iterator(); it.hasNext();){
                int c = it.next();
                if((n & c) == n)
                    it.remove();
            }
            
        }
        
        return answer;
    }
}

• 서술 : 모든 컬럼의 경우의 수를 따져서, 후보키의 특성인 유일성과 최소성 조건을 만족하는 부분집합을 찾는다. 최소성은 식별하는 데 꼭 필요한 속성들로 이루어져 있으므로, 유일성을 만족하는 컬럼 조합이 포함되면 제외해나가면 된다.
• 먼저 유일성을 식별하는 방법은 row의 조합으로 모든 경우의 수 부분집합 row의 컬럼값을 비교하여 모든게 다르면 후보키 List에 추가한다.(유일성 만족)
• 이후 유일성을 만족하는 List를 개수대로 정렬하여 앞에서부터 하나씩 Count하면서 남은 List중 부분집합에 본인이 속하는 경우를 모두 지워준다.