[2019 KAKAO BLIND RECRUITMENT] 후보키

## 접근

---

1. 비트마스크를 사용해서, 모든 조합을 탐색하기 시작한다. 조합마다 HashSet 자료구조를 이용해서 유일성을 만족시키는지 검사한다.

 

 

 

2. 유일성을 만족한다면 최소성도 만족하는지 검사해야 하는데, 기존의 정답들을 담아두는 자료구조와 비교하여 최소성 만족 유무 확인한다.

 

 

 

 

## 해설코드

---

import java.util.*;
import java.io.*;
import java.lang.*;
 
class Solution {
    String[][] r;
    
    boolean check(String s){
        boolean result = true;
        String[] sArr = s.split(" ");
        HashSet<String> hs = new HashSet<String>();
        
        for(int i = 0; i < r.length; i++){
            String tmp = "";
            for(int j = 0; j < sArr.length; j++){
                tmp = tmp + "," + r[i][Integer.valueOf(sArr[j])];
            }
            
            if(hs.contains(tmp)) return false;
            hs.add(tmp);
        }
        
        return result;
    }
    
    public int solution(String[][] relation) {
        int answer = 0;
        int r = relation.length;
        int c = relation[0].length;
        ArrayList<Integer> aList = new ArrayList<>();
        
        for(int i = 1; i < (1 << c); i++){
            HashSet<String> hs = new HashSet<>();
            
            for(int j = 0; j < r; j++){
                String tmp = "";
                
                for(int k = 0; k < c; k++){
                    if((i & (1 << k)) > 0)
                        tmp += relation[j][k];
                }
                
                hs.add(tmp);
            }
            
            if(hs.size() == r){
                boolean flag = true;
                for(int num : aList){
                    if((num & i) == num){
                        flag = false;
                        break;
                    }
                }   
                
                if(flag){
                    answer += 1;
                    aList.add(i);
                }
            }
        }
        
        return answer;
    }
}