[2019 카카오 블라인드] 후보키 (JAVA)

문제

---

풀이

오 이것도 한 번에 풀었다 야호~ 메소드를 분리해서 큰 흐름을 짜 놓고 세부사항을 구현하니 헤메지 않고 차근차근 성공할 수 있었다.

1. findCandidateKeys(): 컬럼 조합의 모든 경우의 수를 구하고 그 키조합이 후보키가 될 수 있는지 확인한다.
2. dfs(): DFS로 조합을 구한다. colCount를 알고 있으니 0부터 colCount - 1까지 숫자의 조합을 구한다.
3. 각 조합 경우의 수에 대해 isUnique()이고 isMinimum()인지 검사한다.
   a. isUnique(): 후보키에 해당하는 컬럼 값을 String으로 이어 붙여 검사에 사용했다. rows에 중복되는 값이 존재하면 false를 리턴한다.
   b. isMinimum(): 현재 검사 중인 key가 이미 후보키인 key를 포함하고 있는 경우를 검사했다. Key 클래스의 내부 메소드에서 attributes를 검사한다.

---

코드

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    
    private String[][] table;
    private int colCount;
    private Set<Key> candidates = new HashSet<>();

    public int solution(String[][] relation) {
        initParams(relation);
        findCandidateKeys();
        return candidates.size();
    }

    private void initParams(String[][] relation) {
        table = relation;
        colCount = relation[0].length;
    }

    private void findCandidateKeys() {
        for (int i = 1; i <= colCount; i++)
            dfs(new int[i], new boolean[colCount], 0, 0, i);
    }

    private void dfs(int[] result, boolean[] visited, int start, int depth, int targetLength) {
        if (depth == targetLength) {
            Key newKey = new Key(Arrays.stream(result).boxed().collect(Collectors.toList()));
            if (isCandidate(newKey)) candidates.add(newKey);
            return;
        }

        for (int i = start; i < colCount; i++) {
            if (!visited[i]) {
                visited[i] = true;
                result[depth] = i;
                dfs(result, visited, i + 1, depth + 1, targetLength);
                visited[i] = false;
                result[depth] = 0;
            }
        }
    }

    private boolean isCandidate(Key key) {
        return isUnique(key) && isMinimum(key);
    }

    private boolean isUnique(Key key) {
        Set<String> rows = new HashSet<>();
        for (int i = 0; i < table.length; i++) {
            String current = "";
            for (int attribute : key.attributes) current += table[i][attribute];
            if (rows.contains(current)) return false;
            rows.add(current);
        }
        return true;
    }

    private boolean isMinimum(Key key) {
        for (Key candidate : candidates)
            if (key.contains(candidate)) return false;
        return true;
    }
}


class Key {
    List<Integer> attributes;

    public Key(List<Integer> attributes) {
        this.attributes = attributes;
    }

    public boolean contains(Key target) {
        for (int attribute : target.attributes)
            if (!this.attributes.contains(attribute)) return false;
        return true;
    }
}