후보키

• Difficulty: Level 2
• Type: Hash/Combination
• link

Solution

• 모든 column combination 을 찾는다.
• 길이가 짧은 column combination 부터 후보키가 될 수 있는지 확인한다.
• Minimality 를 확인하기 위해 이미 등록된 후보키가 확인하는 combination의 subset 이 될 수 없는지 확인한다.
• Uniqueness 를 확인하기 위해 combination 으로 생성된 Counter 의 값들이 모두 1 이하인지 확인한다
• 등록된 후보키 수 가 문제의 답이다

import collections
import itertools

def solution(relation):
    cand_key = []
    length = len(relation[0])
    # Check every possible combination of keys
    for j in range(length+1):
        keys = list(map(list,itertools.combinations(list(range(length)),j)))
        for k in keys:
            # Check for minimality
            if not any(c_k.issubset(k) for c_k in cand_key):
                temp = []
                # Append resulting tuple from key
                for r in relation:
                    temp.append(tuple([r[i] for i in k]))
                # Check for uniqueness
                if all(c <= 1 for c in list(collections.Counter(temp).values())):
                    cand_key.append(set(k))

    return len(cand_key)