[프로그래머스] L2 후보키 / 2019 카카오 블라인드 채용 (Java)

카카오

[프로그래머스] L2 캐시 / 2019 카카오 블라인드 채용

[풀이]

import java.util.*;
class Solution {
    static Set<String> visit = new HashSet<String>(); // 후보키
    static List<Integer> list = new ArrayList<Integer>(); // 조합
    static int answer = 0, size;
    
    public int solution(String[][] relation) {
        size = relation[0].length;
        for(int i=1; i<=size; i++){
            solve(0, i, relation); // i개의 column을 선택하는 조합
        }
        return answer;
    }
    
    static void solve(int idx, int r, String[][] relation){
        if(r == 0) {
            String s = "";
            for(int i=0; i<list.size(); i++){
                s += Integer.toString(list.get(i));
            }
            
            for(String temp : visit){ // 최소성 만족여부(후보키)
                int cnt = temp.length();
                for(int i=0; i<temp.length(); i++){
                    if(s.contains(String.valueOf(temp.charAt(i)))) {
                        cnt--;
                    }
                }
                if(cnt==0) return;
            }
            
            if(isSuccess(relation)){ // 유일성 만족여부
                System.out.println(s);
                visit.add(s);
                answer++;
            }
            System.out.println();
            return;
        } 
 
        for(int i=idx; i<size; i++) {
            list.add(i);
            solve(i+1, r-1, relation);
            list.remove(list.size()-1);
        }
    }
    
    static boolean isSuccess(String[][] relation){
        Set<String> set = new HashSet<String> ();
        for(int i=0; i<relation.length; i++){
            String s = "";
            for(int j=0; j<list.size(); j++){
                int col = list.get(j);
                s += relation[i][col];
            }
            if(set.contains(s))
                return false;
            set.add(s);
        }
        return true;
    }
}