프로그래머스 2019 KAKAO BLIND RECRUITMENT - 후보키[JAVA]

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42890

프로그래머스

풀이 여부: O

dfs로 조합을 구한 코드:

import java.util.ArrayList;
import java.util.List;

class Solution {

    boolean[] visited;
    List<List<Integer>> keyList = new ArrayList<>();
    
    public int solution(String[][] relation) {
        for (int l = 1; l <= relation[0].length; l++) { // l: 조합 길이
            visited = new boolean[relation[0].length];
            dfs(0, l, 0,relation, new ArrayList<>());
        }
        return keyList.size();
    }


    public void dfs(int cur, int len, int idx, String[][] relation, List<Integer> column) {
        if (cur == len) {
            if(check(relation, column)){
                // 유일성을 만족하는 경우 keyList에 이미 존재하는지 확인
                // 이미 존재하면 후보키의 조건인 최소성은 만족하지 못한 것. (길이가 1 부터 조합을 만들어서 최소성을 확인할 수 있다.)
                for (List<Integer> key : keyList) {
                    if(column.containsAll(key)) return;
                }
                keyList.add(column);
                return;
            }

        }
        for (int i = idx; i < relation[0].length; i++) {
            if(visited[i]) continue;
            List<Integer> tmp = new ArrayList<>(column);
            visited[i] = true;
            tmp.add(i);
            dfs(cur + 1, len, i, relation, tmp);
            visited[i] = false;
        }
    }

    // column이 슈퍼 키 조건을 만족하는지 (유일성 check)
    public boolean check(String[][] relation, List<Integer> column) {
        for (int i = 0; i < relation.length; i++) {
            for (int j = i + 1; j < relation.length; j++) {
                StringBuilder sb1 = new StringBuilder();
                StringBuilder sb2 = new StringBuilder();
                for (int c: column) {
                    sb1.append(relation[i][c]);
                    sb2.append(relation[j][c]);
                }
                if (sb1.toString().equals(sb2.toString())) {
                    return false;
                }
            }
        }
        return true;
    }
}


public class Main {

    public static void main(String[] args) {
        Solution sol = new Solution();
        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"}
        };
        int ans = sol.solution(relation);
    }
}

 

bit를 이용해서 조합을 구한 코드:

import java.util.ArrayList;
import java.util.List;

class Solution {

    List<List<Integer>> keyList = new ArrayList<>();
    List<List<Integer>> answer = new ArrayList<>();
    
    public int solution(String[][] relation) {
        for (int i = 1; i < 1 << relation[0].length; i++) {
            int tmp = i;
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j < relation[0].length; j++) {
                int bit = tmp % 2;
                if(bit == 1){
                    list.add(j);
                }
                tmp /= 2;
            }
            if(check(relation, list)){
                keyList.add(list);
            }
        }
        keyList.sort((o1, o2) -> o1.size() - o2.size());
        label : for (List<Integer> list : keyList) {
            for (List<Integer> candidate : answer) {
                if(list.containsAll(candidate)) continue label;
            }
            answer.add(list);
        }
        return answer.size();
    }



    // column이 슈퍼 키 조건을 만족하는지 (유일성 check)
    public boolean check(String[][] relation, List<Integer> column) {
        for (int i = 0; i < relation.length; i++) {
            for (int j = i + 1; j < relation.length; j++) {
                StringBuilder sb1 = new StringBuilder();
                StringBuilder sb2 = new StringBuilder();
                for (int c: column) {
                    sb1.append(relation[i][c]);
                    sb2.append(relation[j][c]);
                }
                if (sb1.toString().equals(sb2.toString())) {
                    return false;
                }
            }
        }
        return true;
    }
}