프로그래머스 후보키 코드 및 해설 (파이썬)

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

코딩테스트 연습 - 후보키

 

candidate_keys라는 리스트에 유일성과 최소성을 모두 만족하는 후보키의 인덱스를 저장합니다.
먼저 key, 혹은 column의 개수를 N으로 저장합니다.

그리고 1에서 N까지 증가하며 각 key의 combination을 구합니다. 이 combination에서 선택된 key들만을 이용해 각 학생을 표현하는 리스트인 current_key를 만들고, 이 current_key가 중복되는 경우 다음 combination으로 넘어갑니다.
하나도 중복되지 않는 경우, 최소성을 확인하기 위해 이미 구한 combination이 지금 구한 combination의 부분집합이 아닌지 확인합니다. 부분집합이 아니라면 current_key에 현재 combination을 추가합니다.
마지막으로 current_key의 길이를 반환합니다.

 

from itertools import combinations

def solution(relation):
    # key의 개수 
    N = len(relation[0])
    key_idx = list(range(N))
    candidate_keys = []
    
    for i in range(1,N+1):
        for comb in combinations(key_idx, i):
            hist = []
            for rel in relation:
                current_key = [rel[c] for c in comb]
                # 하나라도 중복되는 경우: 식별 불가능 
                if current_key in hist:
                    break
                else:
                    hist.append(current_key)
            # 하나도 중복 안 된 경우: 식별 가능
            else:
                for ck in candidate_keys:
                    # 최소성 확인 
                    if set(ck).issubset(set(comb)):
                        break
                else:
                    candidate_keys.append(comb)
    
    return len(candidate_keys)