[프로그래머스] 후보키 / 파이썬

문제 정리

---

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

관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

후보 키의 최대 개수를 구하는 문제입니다.

입출력 예

relation	result
[["100","ryan","music","2"],["200","apeach","math","2"], ["300","tube","computer","3"],["400","con","computer","4"], ["500","muzi","music","3"],["600","apeach","music","2"]]	2

문제풀이

---

총 3단계를 거쳐 후보 키 리스트를 구합니다.
1. 후보키가 될 수 있는 모든 속성들의 조합을 구합니다.
2. 유일성을 만족하는 원소만 거릅니다.
3. 유일성을 만족하는 원소들 중 최소성을 만족하는 원소만 거릅니다.

from itertools import combinations
def make_all_case(relation):
    case_list = []
    col = len(relation[0])
    for i in range(1, col + 1):
        case_list.extend(combinations(range(col),i))    
    return case_list

def filter_unique(lst, relation):
    unique_list = []
    for i in lst:
        tmp_list = []
        for r in relation:
            tmp = []
            for idx in i:
                tmp.append(r[idx])
            tmp_list.append(tuple(tmp))
        if len(set(tmp_list)) == len(relation):
            unique_list.append(i)
    return unique_list

def filter_minimal(lst):
    minimal_list = set(lst)
    for i in range(len(lst)-1):
        for j in range(i+1,len(lst)):
            if set(lst[i]) == set(lst[i]) & set(lst[j]):
                minimal_list.discard(lst[j])
    return minimal_list

def solution(relation):    
    case_list = make_all_case(relation)
    unique_list = filter_unique(case_list, relation)
    candidate_key_list = filter_minimal(unique_list)
    return len(candidate_key_list)