[Programmers] 후보키

.

// 1. 1개가 유일성인 경우 확인
// 2. 1개씩 더해가면서 유일성 체크
// 2.1 유일성이 나오면 추가로 붙는 키들 더해서 wrong에 넣기

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Arrays;

class Solution {
    int row, column;
    String[][] relation;
    HashMap<String, Integer> right = new HashMap<>();
    HashMap<String, Integer> wrong = new HashMap<>();
    
    public int solution(String[][] relation) {
        int answer = 0;
        this.relation = relation;
        row = relation.length;
        column = relation[0].length;
        String[] beforeS = new String[row];
        bfs(beforeS, 0, "", 0);
        answer = right.size();
        return answer;
    }
    
    void bfs(String[] beforeS, int idx, String route, int depth){
        if(depth == row)
            return ;
        for(int j = idx; j < column; j++){
            HashMap<String, Integer> canList = new HashMap<>();
            String[] sumList = new String[row];
            for(int i = 0; i < row; i++){
                sumList[i] = beforeS[i] + " " + relation[i][j];
                canList.put(sumList[i], 1);
            }
            if(canList.size() == row){
                inputRight(route + String.valueOf(j));
            }else{
                bfs(sumList, j+1, route + String.valueOf(j), depth+1);
            }   
        }
    }

    void inputRight(String r){
        boolean[] check = new boolean[column];
        r = sortString(r);
        for(String rEle : r.split("")){
            check[Integer.parseInt(rEle)] = true;
        }
        right.put(r, 0);
        inputNotMini(r, 0, check);
    }
    
    void inputNotMini(String s, int idx, boolean[] check){
        for(int i = idx; i < column; i++){
            if(!check[i]){
                check[i] = true;
                String addS = sortString(s + String.valueOf(i));
                if(right.containsKey(addS)){
                    right.remove(addS);
                }
                wrong.put(addS, 0);
                inputNotMini(addS, i+1, check);
                check[i] = false;
            }
        }
    }
    
    String sortString(String s){
        String sortS = "";
        String[] sArr = s.split("");
        Arrays.sort(sArr);
        for(String sArrEle : sArr){
            sortS += sArrEle;
        }
        return sortS;
    }
}

처음 접근을 잘못해 오래걸린 문제다.

잘못된 접근 : 하나의 row에서 중복된 키들만 HashMap을 통해서 List화 시킨후 중복된 것들만 재귀로 다음 row에서 확인하는 방법을썻더니 틀린 문제가 자꾸 발생했다.

문제 풀이 : 하나의row를 HashMap을 통해서 확인 -> 후보키가 아닐 경우 재귀를 통해 다음 row로 접근 -> 각 row의 key을 합쳐서 하나의 key로 만들어 유일성 학인 -> 만약 유일성이 확보되었을 경우 확보된 키는 right에 넣고, 해당 키와 조합될 수있는 모든 경우를 right에서 확인해 존재할경우 제거함과 동시에 wrong에 넣음