[Python3] Lv2 프로그래머스 - 후보키

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

코딩테스트 연습 - 후보키

- 접근법

후보키의 성질은 다음과 같다.

• 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
• 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

때문에 먼저 모든 Key가 될 수 있는 경우를 조합하여, 그것이 1) 유일성을 만족하는지 검사하고 만족하면 set 타입으로 넣어준다.

 

만족하는 모든 경우의 조합들을 각 set별로 list에 담긴 것들을 2) 최소성을 만족하도록 조절하면 된다. 담긴 set들을 모두 비교하면서 A와 B의 교집합이 A라면, 최소성을 만족하지못하므로 B를 삭제하다보면 유일성을 만족하고 최소성도 만족하는 경우만 남게 될것이다.

 

---

- 소스코드

from collections import defaultdict
from itertools import combinations
def create_dict(relation,idx):
    db_dict=defaultdict(int)
    for i in range(0,len(relation)):
        temp=""
        for x in idx :
            temp+=relation[i][x]
            temp+=str(x)
        db_dict[temp]+=1
        if db_dict[temp]>1 :
            return False
    return True
 
def solution(relation):
    answer = 0
    key_set=[]
    column=[x for x in range(0,len(relation[0]))]
    #유일성 검사
    for i in range(1,len(relation[0])+1) :
        idx=list(combinations(column,i))
        for sets in idx :
            if create_dict(relation,list(sets)) :
                key_set.append(set(sets))
    #최소성 검사
    for current_set in key_set[:] :
        for next_set in key_set[:] :
            if current_set==next_set :
                continue
            if current_set==current_set&next_set :
                key_set.remove(next_set)
    answer=len(key_set)
    return answer