[201113] 후보키 - 2019 KAKAO BLIND RECRUITMENT(level2) ★ 비트마스크 ★

0. 문제 유형 : 조합(완전 탐색, 재귀), 적절한 자료구조(HashSet) / 비트마스크

1. 문제 이해

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

코딩테스트 연습 - 후보키

(1) 주요 요구사항

① String[][] relation : 인적사항 테이블. 후보키 조건을 확인할 대상 데이터베이스

② relation에서 후보키 조건을 만족하는 키의 최대 개수 구하기

- 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되야( = 중복이 없어야)

- 최소성(minimality) : 유일성 가진 키를 구성하는 속성 중 하나라도 제외되면 유일성이 깨지는 것. 유일성에 꼭 필요한 속성들만 포함

 

(2) 제한사항

- relation의 컬럼 길이 : 1이상 8이하, relation의 로우 길이 : 1이상 20이하 → 완전 탐색 활용 가능

- realtion의 문자열 : 1이상 8이하의 길이. 알파벳 소문자, 숫자로만 이루어짐 → 대소문자 구분 신경 안써도 됨

- relation이 모든 튜플은 유일하게 식별 가능 → 후보키는 무조건 1개 이상

 

 

2. 전략

(1) 모든 키의 후보 구하기 : 조합(완전탐색, 재귀)

public void combination(int[] index, int n, int k, int target, ArrayList<String> a, boolean[] visited)

- 컬럼의 index를 대상으로 조합을 구한다.

- nCk (k=1, 2, 3, ... n 인 경우)의 case를 구해서 ArrayList<String>에 담기

esw-csmoon.tistory.com/entry/%EC%88%9C%EC%97%B4%EC%A1%B0%ED%95%A9-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89?category=1125729

① target번째 수의 선택 여부 결정 (단, target의 index가 n보다 작을 때까지만)

- 선택한다면? : 해당 visited를 true로 변경

② target을 옮겨서 재귀 호출 (조합이므로 더이상 앞의 수들은 고려X - 이미 선택여부가 끝난것!!)

③ k가 0이 되면 ArrayList에 넣기( ex> 0, 1 번째 컬럼 선택 → 01 )

 

(2) 후보 키 조건 확인 : HashSet을 통해 유일성 보장

public void checkUnique(ArrayList<String> allCase, String[][] relation, ArrayList<String> candidate)

- 후보 키 조건에 만족하면 ArrayList<String> candidate에 add

 

① 최소성

: 대상 case에 candidate에 있는 어떤 조합이 모두 포함되어 있다면 최소성 위배

- 포함 여부 확인 : String의 contains 이용

- 단, candidate의 문자 하나하나씩 확인해야 됨. 123에 13이 포함된 것을 contains가 바로 잡아낼 수 없음)

② 유일성

: HashSet의 중복 불가능한 성질을 이용

- element : s의 index들에 해당하는 튜플의 속성들을 string으로 연결

- hash.add(element) : element를 HashSet에 add. 중복이 있다면 추가되지 않을 것.

- candidate.add(s) : 만약 hash의 크기와 relation의 row길이가 같다면 중복이 없었던 것이므로 후보 키를 만족

 

 

3. 참고사항

(1) 비트마스크 이용

: 데이터가 늘어난다면 완전 탐색은 감당 불가능

→ 비트마스크를 활용해 조합, 최소성, 유일성 모두에서 시간 단축과 간단화 가능

① 모든 조합

: 각 column의 선택 여부를 0(선택X), 1(선택O)로 나타낸다면 다음과 같을 것

ex> 4개 컬럼(0,1,2,3) 중 1, 2만 선택 → 0110

즉, 1 이상 1<<col 미만의 범위에 존재

 

② 유일성

: ①에서 선택한 컬럼에 맞는 속성만 선택하기(기존 풀이의 element 구하는 과정)

→ & 연산 결과 0보다 크면 해당 컬럼의 속성이라는 뜻

for(int i = 1; i < (1<<col); i++){
    for(int j = 0; j < row; j++){
        String str = "";
        for(int k = 0; k < m; k++){
            if((i & (1<<k)) > 0)	str += relation[j][k];
        }
    }
}

③ 최소성

: candidate ArrayList에 있는 수의 포함여부 확인

→ & 연산 결과 candidate 수와 일치하면 포함 사실을 확인 가능

for(int i = 0; i < candidate.size(); i++){
    if( (candidate.get(i) & str) == candidate.get(i) ) break;
}

 

 

4. 코드

import java.util.*;

class Solution {
    public int solution(String[][] relation) {
        int answer = 0;
        int row = relation.length; int col = relation[0].length;
        ArrayList<String> candidate = new ArrayList<>();
        int[] indexList = new int[col];
        for(int i = 0; i < col; i++)    indexList[i] = i;
        for(int i = 1; i <= col; i++){
            ArrayList<String> allCase = new ArrayList<>();
            combination(indexList, col, i, 0, allCase, new boolean[col]);
            checkUnique(allCase, relation, candidate);
        }
        answer = candidate.size();
        return answer;
    }
    
    public void combination(int[] index, int n, int k, int target, ArrayList<String> a, boolean[] visited){
        if(k==0){
            String s = "";
            for(int i = 0; i < n; i++){
                if(visited[i]) s += index[i];
            }
            a.add(s);
        }
        else{
            if(target < n){
                combination(index, n, k, target+1, a, visited);
                visited[target] = true;
                combination(index, n, k-1, target+1, a, visited);
                visited[target] = false;
            }
        }
    }
    
    public void checkUnique(ArrayList<String> allCase, String[][] relation, ArrayList<String> candidate){
        for(String s : allCase){
            boolean included = false;
            for(String c : candidate){
                int num = 0;
                for(int i = 0; i < c.length(); i++){
                    if(s.contains(c.substring(i, i+1))) num++;
                }
                if(num == c.length()){
                    included = true;
                    break;
                }
            }
            if(included) continue;
            String[] str = s.split("");
            HashSet<String> hash = new HashSet<>();
            for(int i = 0; i < relation.length; i++){
                String element = "";
                for(int j = 0; j < str.length; j++){
                    element += relation[i][Integer.parseInt(str[j])];
                }
                hash.add(element);
            }
            if(hash.size() == relation.length){
                candidate.add(s);
            }
        }
    }
    
}