Lv 2. 후보키

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

프로그래머스

 

비트마스킹을 사용하지 않고 조합생성을 DFS를 통해 수작업했을때 시간초과 오류가 수십번나서 
비트마스킹을 사용하여 문제를 푸는 방법을 공부하였다.
효율성이 엄청나다. 조합짜는시간이 거의 삭제된 느낌

import java.util.*;

public class Solution {
    // 가능한 후보키 조합, 맵, 열 길이
    private List<Integer> candidateKeys = new ArrayList<>();
    private String[][] relation;
    private int columnLength;

    public int solution(String[][] relation) {
        //맵 , 열길이 세팅
        this.relation = relation;
        this.columnLength = relation[0].length;
        //비트마스킹을 통한 조합생성 
        for (int i = 1; i < (1 << columnLength); i++) {
            // 후보키 맞는지 확인
            if (isCandidateKey(i)) {
                candidateKeys.add(i);
            }
        }
        //후보키 조합 set 크기 반환
        return candidateKeys.size();
    }
    //후보키 확인 method  set은 조합번호
    private boolean isCandidateKey(int set) {
        // 유니크 하지않으면 false return;
        if (!isUnique(set)) return false;
        // cadinateKeys 순회돌면서 이미 있는 키면 최소성 만족X
        for (Integer key : candidateKeys) 
            if ((set & key) == key) return false;
        return true;
    }
    //후보키 유일성 체크 method
    private boolean isUnique(int set) {
        //후보키 조합 번호를 가지고 후보키 자격검증 Set에 넣고 비교하면서 검증
        Set<String> tuples = new HashSet<>();
        //하나씩 row를 가져온다.
        for (String[] row : relation) {
            StringBuilder tuple = new StringBuilder();
            //조합을 생성할때와 마찬가지로 컬럼 size만큼 비트마스킹
            for (int j = 0; j < columnLength; j++) {
                //만약 조합번호에 비교하여 선택된 컬럼이면 tuple에 append
                if ((set & (1 << j)) != 0) 
                    tuple.append(row[j]).append(",");
            }
            // set 은 중복허용하지 않으므로 add method는 중복시 false 반환
            if (!tuples.add(tuple.toString())) return false;
        }
        return true;
    }
}