[프로그래머스](Java) - 후보키

문제 링크

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

문제 풀이

다른 분의 풀이를 참고해서 풀었고, 이해가 됬다고 생각했을때 로직을 따라가며 코드를 작성해 보았다.

문제를 풀며 여러가지를 배울 수 있었다. 더 정교한 dfs 로직 및 set의 사용법

그동안 중복된 값을 처리할때는 map을 써왔는데 set도 이제는 잘 사용할 수 있을것 같다.

코드

import java.util.*;

class Solution {
    
    static ArrayList<HashSet<Integer>> candidateKey;
    
    public int solution(String[][] relation) {
        //int answer = 0;
        
        candidateKey = new ArrayList();
        
        int maxlen = relation[0].length;
        
        for(int i=1; i<=relation.length; i++){
            dfs(-1,maxlen-1, 0, i, new HashSet(), relation);
        }
        
        return candidateKey.size();
    }
    
    public static void dfs(int attr, int maxlen, int idx, int size, HashSet<Integer>keySet, String [][] relation){
        
        if(idx==size){
            //종료 조건
            for(HashSet<Integer> key : candidateKey){
                if(keySet.containsAll(key)){
                    return;
                }
            }
        
            if(isUnique(keySet,relation)){
                candidateKey.add(keySet);
            }
            
    
        }
        
        for(int i=attr+1; i<=maxlen; i++){
            HashSet<Integer> newKeySet = new HashSet<>(keySet);
            newKeySet.add(i);
            dfs(i, maxlen, idx+1, size, newKeySet, relation);
            
        }
    }
    
    public static boolean isUnique(HashSet<Integer> keySet, String [][] relation){
        HashMap<String,String> map = new HashMap();
        for(int i=0; i<relation.length; i++){
            String key ="";
            for(int j : keySet){
                
                key += relation[i][j];
            }
            if(map.containsKey(key)){
                return false;
            }else{
                map.put(key,key);
            }
            
        }
        return true;
        
        
    }
}