[프로그래머스] 후보키 python (*)

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

출처 : 프로그래머스

코딩테스트 연습 - 후보키

---

 코드

from itertools import combinations
def solution(relation):
    row = len(relation)
    col = len(relation[0])
    comb = []
    # 모든 후보키 경우의 수 
    for c in range(1, col+1):
        comb.extend(combinations(range(col), c))
    
    candidate_keys = []
    for c in comb:
        tmp = [tuple(rela[cc] for cc in c) for rela in relation]
        # print(tmp)
        # 유일성 : 중복 제거 
        if len(set(tmp)) == row:
            flag = True
            # 최소성
            for k in candidate_keys:
                if set(k).issubset(set(c)):
                    flag = False
                    break
            if flag:
                candidate_keys.append(c)
    return len(candidate_keys)

 풀이

relation의 열과 행의 개수를 모두 구해둔다.

그리고 가능한 후보키의 인덱스 조합을 모두 구해둔다.

후보키를 구할 때는, 유일성을 먼저 고려해보고 유일성을 고려한 조합 중에서 최소성을 만족하는 키만 candidate_keys에 삽입한 후,

이 배열의 길이를 return 해준다.

 

가능한 후보키의 인덱스 조합에 해당하는 relation의 값을 tuple 리스트로 tmp에 저장한다.

tmp에 set()을 적용하여 중복을 제거하고, row와 길이가 같다면 유일성을 만족한다.

이렇게 유일성을 만족하는 조합이 조합의 부분집합인지 issubset()을 사용해 확인한다.

부분집합이면 최소성을 만족하지 않으므로 flag 를 False 로 표시해준다.

 

유일성과 최소성을 모두 만족해야 flag가 True 이다.

이 key만 최종적으로 후보키가 될 수 있다.

 

 배운 점

• issubset() : 부분집합인지 확인
• issuperset() : 상위집합인지 확인