후보키 - 2019 KAKAO BLIND RECRUITMENT (Java, Level 2)

처음 생각

- 컬럼들을 조합하여 한 조합 당 각 컬럼의 문자열을 합친 다음 이를 Set에 삽입한다.

Set의 사이즈가 전체 튜플의 수와 같다면 튜플을 유일하게 식별할 수 있다는 의미이므로 후보키가 되는 컬럼 조합이다.

 

- 모든 컬럼 조합에 대한 유일성 조사를 어떻게 할 것인가?

컬럼이 4개라 하면 0 1 2 3 01 02 03 12 13 23 012 013 023 123 1234처럼 컬럼 갯수가 다른 조합까지 어떻게 식으로 표현해야 하나?

 

- 만일, 유일성을 만족하는 컬럼 조합이 0 01 12 123일 때 어떤 식으로 저장해야 최소성을 검사할 수 있을까? int[]? 새로운 객체? 등등 해결되지 않거나 지나치게 복잡해보이는 흐름이 많았다. 

 

 

참고 풀이

위에서 하던 고민을 해결해주는 개념이 있었다. 바로

비트마스크

비트마스크로 집합을 구현하는 방식을 이용하면 손쉽게(?) 해결할 수 있다.

 

 

열의 갯수를 colNum이라 하면 

0 < k < (1<<colNum)까지의 이진수(컬럼 조합)중에서 유일성과 최소성을 만족하는 k의 갯수를 구한다.

 

checkIfMin()

주어진 숫자가 최소성을 만족하는 지 확인하는 메소드

 

최소성은 기존 키와 현재 키를 & 비트연산하여 확인한다.

& 비트연산한 값이 기존 키와 같다면 현재 키는 최소성을 만족하지 않는다.

 

기존 키가 0011이고 현재 키가 1011이라면 0011 & 1011 = 0011 즉, 기존 키와 값이 같다.

 

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

boolean checkIfMin(int i) {
    for (Integer key : keys) {
        if ((key & i)==key) return false;
    }//for end
    return true;
}

 

solution()

현재 키의 최소성 체크를 먼저 한다.

유일성은 위에서처럼, k 이진수에서 값이 1인 자릿수의 문자열을 붙인 뒤 Set에 넣어 전체 튜플 수와 비교한다.

 

public static int solution(String[][] relation) {
    int rowNum = relation.length; //행수
    int colNum = relation[0].length; //열수

    //한 키당 해당 컬럼의 튜플 값 저장할 set
    Set<String> set = new HashSet<>();
    //키에서 값이 1인 자릿수의 문자열 붙일 sb
    StringBuilder sb = new StringBuilder();

    for (int k = 0; k < (1<<colNum); k++) {
        //현재 키 최소성 체크
        if(!checkIfMin(k)) continue;

        //set 초기화
        set.clear();

        for (int i = 0; i < rowNum; i++) {
            //sb 초기화
           sb.setLength(0);

            for (int j = 0; j < colNum; j++) {

                if (((1<<j) & k) > 0) {
                    //현재 키에서 값이 1인 자릿수에 해당하는 j 인덱스에
                    //해당하는 문자열을 sb에 붙인다.
                    sb.append(relation[i][j]);
                }
            }//for end

            //조립한 문자열을 set에 넣었을 때 false라면
            //유일성이 만족하지 않은 것이므로 해당 key에 대해 break
            if (!set.add(sb.toString())) break;
        }//for end

        //해당 키에서의 set 사이즈가 튜플의 수와 같다면
        //유일성 만족하므로 후보키 저장 리스트에 추가
        if(set.size()==rowNum) keys.add(k);
    }//for end

    return keys.size();
}//solution() end

 

---

참고

https://girawhale.tistory.com/102