[Programmers] 2019 KAKAO BLIND RECRUITMENT - 후보키 (Python)

 

코딩테스트 연습 - 후보키

 

 

데이터베이스에서 사용할 수 있는 후보키의 개수를 구하는 문제!

효율적으로 보이지는 않지만 후보키의 개수가 많이 않기 때문에 combinations을 사용해서 구해도 충분히 시간안에 해결 가능한 문제였다!

 

 

from itertools import combinations

def solution(relation):
    answer = 0
    n = len(relation[0]) # attributes 수

    keys = []
    # 가능한 키 모두 구하기
    for comb in list(list(combinations(range(n),  i)) for i in range(1, n+1)) : # 가능한 feature 조합
        for case in comb : 
            tmp = ["" for _ in range(len(relation))]
            for i in case :
                for j in range(len(relation)) :
                    tmp[j] = tmp[j] + relation[j][i]
                    
            att_set = set(tmp)
            if len(att_set) == len(relation) :
                keys.append(case)
    
    # 키 중에서 후보키만 필터링
    candidates = []
    for i in keys :
        flag = True
        for j in candidates :
            if len(set(i) & set(j)) == len(set(j)) :
                flag = False
                break
        if flag :
            candidates.append(i)
    answer = len(candidates)

    return answer