[PS] 후보키

문제 링크

코드

def solution(relation):
    cases = create_cases(len(relation[0]))
    unique_key = get_candidates(relation, cases)
    return len(unique_key)
    

def create_cases(length):
    cases = []
    for i in range(1, length + 1):
        
        
        def pick(picked, left, length):
            if len(picked) == length:
                cases.append(picked)
                return
            if left:
                pick(picked, left[1:], length)
                pick(picked | {left[0]}, left[1:], length)
                
        
        pick(set(), [i for i in range(length)], i)
    return cases


def get_candidates(relation, cases):
    candidates = []
    while cases:
        key = cases.pop(0)
        if is_unique(relation, key):
            candidates.append(key)
            
            temp = []
            for case in cases:
                if not case > key:
                    temp.append(case)
            cases = temp
        
    return candidates


def is_unique(relation, case):
    row = list(map(lambda x: tuple([x[i] for i in case]), relation))
    return len(row) == len(set(row))

리뷰

• 모든 케이스를 구한 다음에 이 케이스가 후보키의 조건을 만족하는지 확인하는 방식으로 풀었다.
• itertools의 combination 함수를 이용하면 더 쉽게 모든 케이스를 구할 수 있다.