2019 KAKAO 코딩테스트 후보키

https://programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

 

후보키들을 찾는 문제이다.

입력의 크기가 크지 않아서(column <= 8, row <= 20) 모든 column조합을 확인하는 완전탐색으로도 가능하다. 
   $$ \sum_{n=1}^{8} \binom{8}{n}  = 255 $$

확인하려는 column들의 index 항목만 가지게 relation속 tuple을 재가공하고,
이 재가공된 tuple들의 중복여부를 확인하면 된다. (유일성 확인)

나는 python set 을 사용하여 중복되는 tuple들에 대해서 처리하였다.
재가공한 tuple들을 set에 넣어 len(set) == len(relation) 이라면 해당 column조합은 후보키가 될 수 있다.

마지막으로 해당 column조합이 기존의 후보키 + a 의 조합으로 이뤄져있는지 확인하고 (최소성 확인) 최소성이 확인되면, 후보키 리스트에 추가하면 된다.

 

내 코드는 다음과 같다

import itertools

def solution(relation):
    
    answer = 0
    c_cnt = len(relation[0])
    candidate_keys = []
    
    def check(keys):
        for C in candidate_keys:
            if all(c in keys for c in C):
                return True
        return False
    
    
    for cnt in range(1,c_cnt+1):
        for keys in itertools.combinations([i for i in range(c_cnt)], cnt):
            if check(keys):
                continue

            s = set()
            for r in relation:
                s.add(tuple([r[key] for key in keys]))
            if len(s) == len(relation):
                candidate_keys.append(keys)

    return len(candidate_keys)