프로그래머스-후보키

프로그래머스 - 후보키

---

문제 설명

---

문제 풀이

풀이 설명

유일성, 최소성을 만족할려면 중복의 여부를 판단해야한다
중복은 로직의 결과를 Map에 담아 주어진 Row 개수와 Map의 길이가 같은지 확인

유일성을 만족하는 Key 찾기
주어진 데이터에서 Col 기준으로 중복 여부가 없으면 유일한 Key로 판단

최소성을 만족하는 Key 찾기
유일성을 만족하는 Key를 제외 후, 경우의 수로 Key를 찾음

학번 | 이름 | 학년 | 전공
위 테이블 중 학번이 유일성을 만족하는 Key
나머지 이름 | 학년 | 전공 에서 최소성을 찾아야 할때

이름 | 학년 
이름 | 전공
학년 | 전공
이름 | 학년 | 전공

위와 같이 조합할 수 있는 경우의 수를 찾은 후
그 결과가 중복하지 않는 Key인 경우 최소성 으로 판단

최소성을 찾을 때 주의할 점

D | E
A | C | D
A | C | E
위 케이스는 3개다 최소성을 만족함

테스트 케이스

        solution.solution(new String[][]{
                {"100","ryan","music","2"}
                ,{"200","apeach","math","2"}
                ,{"300","tube","computer","3"}
                ,{"400","con","computer","4"}
                ,{"500","muzi","music","3"}
                ,{"600","apeach","music","2"}
        });

        solution.solution(new String[][]{
                {"a","1","aaa","c","ng"},
                {"a","1","bbb","e","g"},
                {"c","1","aaa","d","ng"},
                {"d","2","bbb","d","ng"}});

코드 작성

        int count = 0;
        String[][] inputList = null;
        List<int[]> combinationList = null;
        List<int[]> outputList = null;

        public int solution(String[][] relation) {
            count = 0;
            inputList = relation;
            outputList = new ArrayList<>();

            findUniqueKey();
            findMinimalityKey();

            int answer = count;
            System.out.println("answer = " + answer);
            return answer;
        }

        void findUniqueKey(){
            for (int i = 0; i < inputList[0].length; i++){
                checkDuplicated(new int[]{i});
            }
        }


        void findMinimalityKey(){
            if(2 > inputList.length) return;

            int combineCount = 2;
            List<Integer> list = outputList.stream().filter(z -> z.length == 1).map(z -> Arrays.stream(z).boxed().collect(Collectors.toList())).flatMap(z -> z.stream()).collect(Collectors.toList());
            int[] arr = IntStream.range(0, inputList[0].length).filter(x -> list.indexOf(x) < 0).toArray();

            while (combineCount <= inputList[0].length){
                combinationList = new ArrayList<>();
                combination(arr, new boolean[arr.length], 0, arr.length, combineCount);

                for(int i = 0; i < combinationList.size(); i++){
                    checkDuplicated(combinationList.get(i));
                }

                combineCount++;
            }
        }

        void checkDuplicated(int[] arr){
            Map<String, String> duplicate = new HashMap<>();
            String combineKeys = "";

            for(int i = 0; i < inputList.length; i++) {
                for(int j = 0; j < arr.length; j++){
                    combineKeys += inputList[i][arr[j]];
                }

                duplicate.put(combineKeys, combineKeys);
                combineKeys = "";
            }

            if(duplicate.size() == inputList.length) {
                if(!isMinimality(arr)){
                    count++;
                    outputList.add(arr);
                }
            }
        }

        void combination(int[] arr, boolean[] visited, int depth, int n, int r) {
            if (r == 0) {
                List<Integer> temp = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    if (visited[i]) {
                        temp.add(0,arr[i]);
                    }
                }
                combinationList.add(0, temp.stream().mapToInt(Integer::intValue).toArray());
                return;
            }

            if (depth == n) {
                return;
            }

            visited[depth] = true;
            combination(arr, visited, depth + 1, n, r - 1);

            visited[depth] = false;
            combination(arr, visited, depth + 1, n, r);
        }

        boolean isMinimality(int[] arr){
            return outputList.stream().filter(x -> x.length > 1).map(x -> hasAllElement(x, arr)).anyMatch(x -> x == true);
        }

        boolean hasAllElement(int[] arr1, int[] arr2){
            int sameCount = 0;

            for(int i = 0; i < arr1.length; i++){
                for(int j = 0; j < arr2.length; j++){
                    if(arr1[i] == arr2[j]){
                        sameCount++;
                    }
                }
            }

            return sameCount == arr1.length ? true : false;
        }