2019 - 후보키

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

코딩테스트 연습 - 후보키

[ 문제풀이 ]

주어진 속성들의 모든 조합에 대해서 후보키의 조건인 유일성과 최소성을 만족하는지 판단하면 되는 문제이다.

​유일성과 최소성을 판단하는 것은 어렵지 않을 것이지만 주어진 모든 속성들의 조합을 구현하는 것이 조금 난해할 수도 있다. 이는 비트 마스킹(Bit Masking) 기법을 사용하면 쉽게 구현할 수 있다.

​비트 마스킹 기법은 간단하게 정수의 2진수 표현을 자료구조로 활용하는 방법이다. 예를 들어 다음과 같은 4개의 속성을 가지는 테이블이 있다고 하자.

4개의 속성으로 만들 수 있는 조합은 총 2^4인 16개이다. 2^4, 이 표현을 보면 뭔가 2진수와 관련이 있어 보이지 않는가? 0부터 16을 2진수인 '0000' ~ '1111'로 표현해보자. 0과 1은 흔히 On/Off처럼 2개의 상태를 표현할 수 있다.

​각 비트의 자리에 속성을 한 개씩 매칭해보자.

슬슬 무슨 비트 마스킹을 활용한다는 것이 어떤 의미인지 알 것이다. 예를 들어 {학번, 이름} 속성의 조합을 표현한다면 어떻게 할까? '1100'으로 표현할 수 있다. {학번, 전공, 학년} 속성의 조합은 '1011'로 표현할 수 있다.

​즉, 공집합을 제외한 n 개의 속성으로 가능한 조합은 1 ~ (1 << n)으로 표현할 수 있다. 이후 모든 조합에 대해서 유일성과 최소성을 판단해주면 된다.

import java.util.*;

class Solution { 
    
    List<Integer> candidateKey;
    int cols;
       
    public int solution(String[][] relation) {
        candidateKey = new LinkedList<>();
        cols = relation[0].length;
        
        //모든 속성의 조합 유일성 확인 '00 … 01' ~ '11 … 11'
        for (int i = 1; i < 1 << cols; ++i) {
            if (isUniqueness(i, relation)) {
                candidateKey.add(i);
            }
        }
        
        //유일성을 만족하는 속성의 조합 최소성 확인
        isMinimality();
        return candidateKey.size();
    }
    
    public boolean isUniqueness(int key, String[][] relation) {
        //모든 튜플을 비교
        for (int i = 0; i < relation.length - 1; ++i) {
            for (int j = i + 1; j < relation.length; ++j) {
                boolean flag = true;
                //모든 속성을 비교
                for (int k = 0; k < relation[0].length; ++k) {
                    //k번째 속성이 키의 속성이 아니라면
                    if ((key & (1 << k)) == 0) continue;
                    
                    //현재 Key가 두 튜플을 구분하기 때문에 더이상 비교 x
                    if (!relation[i][k].equals(relation[j][k])) {
                        flag = false;
                        break;
                    }
                }
                
                //두 튜플을 구분하지 못하기 때문에 유일성 만족 x        
                if (flag) {
                    return false;
                }
            }
        }          
        return true;
    }
    
    public void isMinimality() {
        for (int i = 0; i < candidateKey.size(); ++i) {
            int key = candidateKey.get(i);
            for (int j = i + 1; j < candidateKey.size(); ) {
                int key2 = candidateKey.get(j);
                //key의 속성이 key2에 모두 있으면 최소성을 만족하지 않기 때문에 key2를 제거
                if ((key & key2) == key) {
                    candidateKey.remove(j);
                } else {
                    ++j;
                }
            }
        }
    }
}