programmers_후보키_java

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

프로그래머스

import java.util.*;

class Solution {
    public int solution(String[][] relation) {
        int answer = 0;

        int relationLength = relation.length;
        int attributeLength = relation[0].length;

        List<Set<Integer>> candidates = new ArrayList<>();
        int[] idx = new int[attributeLength];

        candidateKey(idx, 0, 0, relation, relationLength, attributeLength, candidates);

        for (Set<Integer> s : candidates){
            System.out.println(s.toString());
        }
        answer = candidates.size();
        return answer;
    }

    // 후보키 가능한 집합 찾기
    public void candidateKey(int[] idx, int cnt, int start,String[][] relation, int relationLength, int attributeLength, List<Set<Integer>> candidates){
        if (cnt == attributeLength){
            return;
        }

        for (int i = start; i<attributeLength; i++){
            idx[cnt] = i;

            boolean res = isCandidateKey(idx, cnt+1, relation, relationLength); // 후보키가 되는지
            if (!res){ // 후보키가 안되는 경우
                candidateKey(idx, cnt+1, i+1, relation, relationLength, attributeLength, candidates);
            }else { // 후보키인 경우
                Set<Integer> nowIdx = idexToSet(idx, 0, cnt+1);
                boolean isCandidtate = true;
                for (int j = 0; j<candidates.size(); j++){
                    Set<Integer> now = candidates.get(j);
                    if (now.size() > nowIdx.size()){ // 기존의 것이 더 큰경우
                        if (now.containsAll(nowIdx)){
                            candidates.remove(j);
                            j--;
                        }
                    }else if(now.size() < nowIdx.size()){
                        if (nowIdx.containsAll(now)){
                            isCandidtate = false;
                        }
                    }
                }
                if (isCandidtate){
                    candidates.add(nowIdx);
                }
            }
        }
    }

    // 해당 인덱스들이 후보키가 될 수 있는지
    public boolean isCandidateKey(int[] idx, int size, String[][] relation, int relationLength){
        Set<String> set = new HashSet<>();
        for (int i =0; i< relationLength; i++){
            // 선정한 속성들의 값 중복 확인
            StringBuilder word = new StringBuilder();
            for (int j = 0; j<size; j++){
                word.append(relation[i][idx[j]]);
            }
            if (set.contains(word.toString())){
                return false;
            }
            set.add(word.toString());
        }

        return true;
    }

    // 인덱스를 String으로 변경
    public Set<Integer> idexToSet(int[] idx, int start, int size){
        Set<Integer> set = new HashSet<>();
        for (int i = start; i< size; i++){
            set.add(idx[i]);
        }
        return set;
    }
}