[코딩테스트] 프로그래머스 42890, 후보키

문제

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

프로그래머스

 

문제 접근

1. n개의 컬럼이 만들수 있는 조합을 계산합니다.
   • 예를 들어 4개의 컬럼의 조합수는 4C1 + 4C2 + 4C3 + 4C4 = 15 입니다.
2. 유일키를 만족하는 후보키 조합을 탐색합니다.
   • 유일키를 만족하는 조건은 해당 컬럼들의 문자열을 생성하였을 경우 중복되지 않아서 relation 2차원 배열의 행수와 동일해야 합니다.
3. 최소성을 만족하는 후보키 조합을 탐색합니다.
   • 최소성을 만족하는 조건은 유일성을 만족하는 컬럼들을 포함하고 있지 않다면 최소성을 만족합니다.
   • 예를 들어 유일성을 만족하는 컬럼 조합이 "01"이라면 최소성을 만족하지 못하는 컬럼 조합은 "012", "021" 등이 존재합니다.

구현

import java.util.*;

class Solution {
    private static List<String> list = new ArrayList<>();

    public int solution(String[][] relation) {

        int n = relation[0].length;
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = i;
        }

        // 1. 컬럼들에 대한 조합 생성
        for(int i = 1; i <= n; i++){
            boolean[] chosen = new boolean[n];
            combination(arr, n, i, 0, chosen);
        }

        // 2. 유일성을 만족하는 후보키 조합 탐색
        List<String> unique = new ArrayList<>();
        for(int i = 0; i < list.size(); i++){
            if(isUnique(list.get(i), relation)){
                unique.add(list.get(i));
            }
        }

        // 3. 최소성을 만족하는 후보키 조합 탐색
        List<String> minimum = new ArrayList<>(unique);
        for(int i = 0; i < unique.size(); i++){
            String start = unique.get(i);
            for(int j = 0; j < unique.size(); j++){
                String target = unique.get(j);

                if(start.equals(target)){
                    continue;
                }

                int cnt = 0;
                for(char c : start.toCharArray()){
                    if(target.contains(String.valueOf(c))){
                        cnt++;
                    }
                }
                if(cnt == start.length()){
                    minimum.remove(target);
                }
            }
        }

        return minimum.size();
    }


    public boolean isUnique(String columns, String[][] relation) {
        Set<String> set = new HashSet<>();
        for(String[] record : relation){
            String value = "";
            for(char column : columns.toCharArray()){
                value += record[Integer.parseInt(String.valueOf(column))];
            }
            set.add(value);
        }
        if(set.size() == relation.length){
            return true;
        }
        return false;
    }


    public void combination(int[] arr, int n, int r, int i, boolean[] chosen) {
        if(i == r){
            StringBuilder sb = new StringBuilder();
            for(int j = 0; j < chosen.length; j++){
                if(chosen[j]){
                    sb.append(arr[j]);
                }
            }
            if(sb.length() > 0 && !list.contains(sb.toString())) {
                list.add(sb.toString());
            }
            return;
        }

        chosen[i] = true;
        combination(arr, n, r, i+1, chosen);
        chosen[i] = false;
        combination(arr, n, r, i+1, chosen);
    }

    public static void main(String[] args){

        String[][] relation = {{"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 s = new Solution();
        int answer = s.solution(relation);
        System.out.println(answer);
    }
}