[Python/프로그래머스]후보키_조합

 

 

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

프로그래머스

 

 

 

어떻게 푸는지 잘 감이 안왔는데...

combinations를 쓰는건가 생각했는데 맞았다. 

 

 

combinations는 반환 값이 튜플이다. 

 

 

 

 

1. combinations를 이용해서 조합을 모두 구한다.

2. 유일성을 만족하는 친구를 찾는다. -> 1번에서 구한 친구들을 이용해 relation값들을 이용해서

튜플을 만들고 그것의 set(중복제거)후의  길이가 relation의 길이와 동일하면 모두 식별할 수 있음을 의미 

3. 최소성을 만족하는 친구를 찾는다. -> 유일성을 만족하는 친구들을 돌면서 만약 부분집합을 발견한다면 discard해준다. 

remove는 없으면 에러나는데 discard는 없어도 에러안난다. 

4. answer에 남아있는 값들의 길이를 반환해준다. 

 

 

 

 

 

코드 : 

from itertools import combinations 

def solution(relation):
    row = len(relation)
    col = len(relation[0])
    
    
    combi = []
    for i in range(1,col+1) :
    	# 그냥 col하면 안되고 range(col)해야한다.
        # col까지의 숫자중에서 i개를 조합으로 뽑는다.
        combi.extend(combinations(range(col),i))
    # 유일성 
    unique = []
    for i in combi :
        tmp = [tuple(item[key] for key in i) for item in relation]
        if len(set(tmp)) == row :
            unique.append(i)
    # 최소성 
    answer = set(unique)
    for i in range(len(unique)) :
        for j in range(i+1, len(unique)) :
            # 부분집합이 있다면 
            if len(unique[i]) == len(set(unique[i]) & set(unique[j])) :
                # 삭제 
                answer.discard(unique[j])
    return len(answer)