후보키.md

🔑 후보키

난이도: Lv.2
소요 시간: 97분
메모리: --KB
시간: --ms

리뷰

• 조합 + dfs로 풀었는데,, 뭔가 더 효율적이고 좋게 풀 수 있을 거 같은데,,
• 모르겠다.. @_@

전체 코드

import java.util.HashSet;
import java.util.Set;

class Solution_후보키 {
    String[][] relations;
    Set<String> candidateKey;
    char[] zero_arr;
    int column, N, answer;

    int solution(String[][] relation) {

       relations = relation;
        column = relation[0].length;
        N = relation.length;
        candidateKey = new HashSet<>();

        answer = 0;
        zero_arr = new char[column];
        for (int i = 0; i < column; i++) {
            zero_arr[i] = '0';
        }
        for (int size = 1; size <= column; size++) {
            checkCandidate(size, 0, 0, zero_arr.clone());
        }
        return answer;
    }

   void checkCandidate(int size , int cnt, int st_idx, char[] checked){
        if (size == cnt) {
            int[] arr = new int[size];
            int arr_size = 0;
            for (int j = 0; j < column; j++) {
                if (checked[j] == '1') {
                    arr[arr_size++] = j;
                }
            }

            Set<String> set = new HashSet<>();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < N; i++) {
                sb.setLength(0);
                for (int j = 0; j < arr_size; j++) {
                    sb.append(relations[i][arr[j]]).append(" ");
                }
                if (set.contains(sb.toString())) {
                    return;
                } else {
                    set.add(sb.toString());
                }
            }

            candidateKey.add(String.valueOf(checked));
            answer++;
            return;
        }

        if (cnt + column - st_idx < size) return;

        for (int i = st_idx; i < column; i++) {
            char[] key = zero_arr.clone();
            key[i] = '1';
            if (!checkTarget(i, 0, key, checked)) continue;

            checked[i] = '1';
            checkCandidate(size, cnt + 1, i + 1, checked);
            checked[i] = '0';
        }
    }

    boolean checkTarget(int target, int st, char[] key, char[] checked){

         if (candidateKey.contains(String.valueOf(key))) {
            return false;
        }

        for (int i = st; i < target; i++) {
            if (checked[i] == '1') {
                key[i] = '1';
                if (!checkTarget(target, i + 1, key, checked)) return false;
                key[i] = '0';
            }
        }

        return true;
    }
}