[프로그래머스] 후보키 - JAVA

문제 사이트

유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

유일성을 만족하는지 확인한 후 최소성을 확인하여 후보키를 찾아내야한다.

1. dfs를 사용해서 후보키 조합을 만든다.
   • 조건중에 column의 개수가 8개 이하 이므로 int형의 비트마스킹을 도입할 수 있다.
2. 후보키 조합을 작은 단위부터 검사하여 후보키를 만족한 요소의 리스트를 만들고 이후 검사하는 조합의 요소가 리스트에 들어있다면 건너뛴다.
3. 후보키 리스트의 크기를 반환한다.

class Solution {
    public int solution(String[][] relation) {
        int colSize = relation[0].length;
        int rowSize = relation.length;
        
        List<Integer> combinations = new ArrayList<>();
        for (int i = 1; i < (1 << colSize); i++) {
            combinations.add(i);
        }
        

        combinations.sort(Comparator.comparingInt(Integer::bitCount));
        

        List<Integer> candidateKeys = new ArrayList<>();
        

        for (int comb : combinations) {
            

            if (!isMinimal(comb, candidateKeys)) {
                continue; 
            }
            

            if (isUnique(comb, relation, rowSize, colSize)) {
                candidateKeys.add(comb); 
            }
        }
        
        return candidateKeys.size();
    }
    

    private boolean isMinimal(int comb, List<Integer> candidateKeys) {
		//todo
    }
    
    private boolean isUnique(int comb, String[][] relation, int rowSize, int colSize) {
		//todo
    }
}

유일성

1. 조합에 해당하는 요소를 하나의 문자열로 만들어 set에 저장한다.
2. set의 크기와 relation의 rowSize가 같다면 유일성이 만족된다.

    private boolean isUnique(int comb, String[][] relation, int rowSize, int colSize) {
        Set<String> set = new HashSet<>();
        
        for (int i = 0; i < rowSize; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < colSize; j++) {

                if (((comb >> j) & 1) == 1) {
                    sb.append(relation[i][j]).append(","); 
                }
            }
            set.add(sb.toString());
        }
        

        return set.size() == rowSize;
    }

최소성

1. 현재 comb는 비트 카운트를 기준으로 오름차순으로 되어있다.
2. 비트 카운트가 작은 조합을 우선적으로 candiateKeys에 넣는다.
3. 이후 검사하는 comb에 대해서 candiateKeys에 해당 조합이 포함되는지 검사하며 진행한다.

    private boolean isMinimal(int comb, List<Integer> candidateKeys) {
        for (int key : candidateKeys) {
            if ((key & comb) == key) {
                return false; 
            }
        }
        return true;
    }

전체 코드

import java.util.*;

class Solution {
    public int solution(String[][] relation) {
        int colSize = relation[0].length;
        int rowSize = relation.length;
        
        List<Integer> combinations = new ArrayList<>();
        for (int i = 1; i < (1 << colSize); i++) {
            combinations.add(i);
        }
        

        combinations.sort(Comparator.comparingInt(Integer::bitCount));
        

        List<Integer> candidateKeys = new ArrayList<>();
        

        for (int comb : combinations) {
            

            if (!isMinimal(comb, candidateKeys)) {
                continue; 
            }
            

            if (isUnique(comb, relation, rowSize, colSize)) {
                candidateKeys.add(comb); 
            }
        }
        
        return candidateKeys.size();
    }
    

    private boolean isMinimal(int comb, List<Integer> candidateKeys) {
        for (int key : candidateKeys) {
            if ((key & comb) == key) {
                return false; 
            }
        }
        return true;
    }
    
    private boolean isUnique(int comb, String[][] relation, int rowSize, int colSize) {
        Set<String> set = new HashSet<>();
        
        for (int i = 0; i < rowSize; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < colSize; j++) {

                if (((comb >> j) & 1) == 1) {
                    sb.append(relation[i][j]).append(","); 
                }
            }
            set.add(sb.toString());
        }
        

        return set.size() == rowSize;
    }
}