2019 KAKAO BLIND RECRUITMENT - 후보키 (Level 2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from itertools import combinations

def solution(relation):
    def validate_candidate_key(candidate_keys, comb, n_uniques):
        ## 1. Check uniqueness
        if n_uniques == n_rows:
            ## 2. Check minimality
            for key in candidate_keys:
                if key.issubset(comb):
                    break
            else:
                return True
        return False

    n_rows = len(relation)
    n_cols = len(relation[0])
    dics   = {colname: [row[colname] for row in relation] for colname in range(n_cols)}

    candidate_keys = []
    for size in range(1, n_cols+1):
        for comb in combinations(dics, size):
            comb = set(comb)
            vals = {tup for tup in zip(*[dics[col] for col in comb])}
            if validate_candidate_key(candidate_keys, comb, len(vals)):
                candidate_keys.append(comb)
    return len(candidate_keys)