+1 2019 KAKAO BLIND RECRUITMENT 후보키

import java.util.*;

class Solution {
    static String[][] relation;
    static Set<String> set;
    
    public int solution(String[][] relation) {
        this.relation = relation;
        set = new HashSet<>();
        
        for(int i=1; i<=relation[0].length; i++){
            boolean[] visited = new boolean[relation[0].length];
            dfs(0,0,i,visited);
            
        }
        
        return set.size();
    }
    // TODO: static 없이 실행해보기
    public static void dfs(int idx, int cnt, int target, boolean[] visited){
        if(cnt == target){
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<visited.length; i++){
                if(visited[i]){
                    sb.append(i);
                }
            }
            String cols = sb.toString();
            if(isPossible(cols,visited)){
                set.add(cols);
            }
            return;
        }
        
        if(idx>=visited.length) return;
        
        // back tracking section
        visited[idx] = true;
        dfs(idx+1, cnt+1,target, visited);
        
        visited[idx] = false;
        dfs(idx+1, cnt, target ,visited); // 이거 땜에 계속 틀렸다.
    }
    
    public static boolean isPossible(String cols, boolean[] visited){
        
        // 최소성 만족 확인
        for(String s: set){
            boolean flag = true;
            for(int i=0; i<s.length(); i++){
                if(!cols.contains(s.charAt(i)+"")){
                    flag = false; 
                }
            }
            if(flag){
                // 기존에 있던 후보키의 원소 모두 포함시 최소성 불만족
                return false;
            }
        }
        
        Set<String> sameSet = new HashSet<>(); // 후보키로서의 유일성을 보장하는지 검증하는 set
        int[] col_idxes = new int[cols.length()];
        int idx = 0;
        for(int i=0; i<visited.length; i++){
            if(visited[i]){
                col_idxes[idx++] = i;
            }
        }
        
        for(int i=0; i<relation.length; i++){
            StringBuilder sb = new StringBuilder();
            for(int j=0; j< col_idxes.length; j++){
                sb.append(relation[i][col_idxes[j]]);
            }
            String data = sb.toString();
            if(sameSet.contains(data)){
                return false;
            }else{
                sameSet.add(data);
            }
        }
        return true;
        
    }
    
}

1. 백트래킹으로 가능한 모든 조합 구하기 + 백트래킹시 조건에 맞는 것만 카운트하기
2. 후보키가 되기 위해서는 최소성(키 중 하나 빼도 키로서 작용), 유일성(키로 조회시 중복 레코드 없음)을 만족해야한다.

두번째

import java.util.*;

class Solution {
    String[][] relation;
    Set<String> set;
    boolean[] visited;
    
    public int solution(String[][] relation) {
        this.relation = relation;
        set = new HashSet<>();
        
        // 조합 만들기 위해서 idx 한칸씩 뛰어 가며 dfs실행한다.
        for(int i=0; i<relation[0].length; i++){
            visited = new boolean[relation[0].length];
            dfs(0,0,i+1);
        }
        
        return set.size();
    }
    
    public void dfs(int curIdx, int accNum,int targetNum)
    {   // 종료 조건
        if(accNum == targetNum){
            StringBuilder sb = new StringBuilder();
            // 조합된 (방문한)키 조회 하여 키 생성
            for(int i=0; i<visited.length; i++){
                if(visited[i]) sb.append(i);
            }
            String curKey = sb.toString();
            // 현재 키가 최소성, 유일성 만족하면 후보키 셋에 등록
            if(isValidKey(curKey)) set.add(curKey);
        }
        
        if (curIdx >= visited.length) return; // 인덱스 넘어가면 종료
        
        // 키 갱신 영역
        visited[curIdx] = true; // 현재 인덱스 포함
        dfs(curIdx+1, accNum+1, targetNum);
        
        visited[curIdx] = false; // 현재 인덱스 미포함 처리
        dfs(curIdx+1, accNum, targetNum);
    }
    
    public boolean isValidKey(String curKey){
        System.out.println("here1");
        // 최소성 검증
        for(String s: set){
            boolean flag = true;
            for(int i=0; i<s.length(); i++){
                if(!curKey.contains(s.charAt(i)+"")) flag = false;
            }
            if(flag) return false;
        }
        
        //선택된 키 인덱스 등록
        int[] key_pos = new int[curKey.length()];
        for(int i=0; i<curKey.length(); i++){
            key_pos[i] = Integer.parseInt(curKey.charAt(i)+"");
            
        }
        
        // 유일성 검증
        Set<String> check = new HashSet<>(); // 중복되는 키 있는지 확인 
        
        for(int i=0; i<relation.length; i++){
            String[] curRow = relation[i];
            StringBuilder sb = new StringBuilder();
            for(int keyIdx : key_pos){
                sb.append(curRow[keyIdx]);
            }
            String tmpKey = sb.toString();
            if(check.contains(tmpKey)) return false; // 유일성 만족 못 하는 경우
            check.add(tmpKey);
        }
        
        return true; // 유일성, 최소성 모두 만족
    }

}

Integer.valueOf -> Integer 반환, Integer.parseInt -> int반환
이때 parseInt는 인자로 String이 오고 char는 오지 못함
valueOf에 char를 넣으면 아스키코드 값으로 변경한다.