(Python/LV2) 후보키 코드

문제 출처:https://school.programmers.co.kr/learn/courses/30/lessons/42890

풀이: 

 

첫 시도:

from itertools import combinations

def solution(relation):
    row = len(relation) # 행
    col = len(relation[0]) # 열

    #가능한 속성의 모든 인덱스 조합
    combi = []
    for i in range(1, col+1):
        combi.extend(combinations(range(col), i))
    arr = set()
    for i in combi:
        tmp = [tuple([item[key] for key in i]) for item in relation]
        if row == len(set(tmp)): # 겹치는게 없으니 열이 같다 >> 중복된 값이 없음 # 유일성
            arr.add(i)

    res = set()
    idxx = 0
    idx =set({idxx})
    while idxx != col+1:
        flag =True
        for i in arr:
            if idx.issubset(set(arr)):
                flag = False
                break
        if flag:res.add(i)
        idxx += 1
    return len(res)

from itertools import combinations

def solution(relation):
    row = len(relation) # 행
    col = len(relation[0]) # 열

    #가능한 속성의 모든 인덱스 조합
    combi = []
    for i in range(1, col+1):
        combi.extend(combinations(range(col), i))
        
    arr = set()
    res = []
    
    for i in combi:
        tmp = [tuple([item[key] for key in i]) for item in relation]
        if row == len(set(tmp)): # 겹치는게 없으니 열이 같다 >> 중복된 값이 없음 # 유일성
            arr.add(i)
            # 유일성 통과하면 희소성
            flag = True
            for j in res:
                if set(j).issubset(set(i)): # 겹치는게 있으면
                    flag = False
            if flag: # 맨 처음 빈 리스트일때 넣음 / 희소성일때 넣음
                res.append(i)
    return len(res)

 

 

#가능한 속성의 모든 인덱스 조합
combi = []
for i in range(1, col+1):
    combi.extend(combinations(range(col), i))
    
    
    
# >>[(0,), (1,), (2,), (3,), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3), (0, 1, 2, 3)]

이런식으로 조합이 나옴 

 

 

 

for i in combi:
    tmp = [tuple([item[key] for key in i]) for item in relation]

그럼 0 / 1 / ..  / 0,1,2,3 / 조합을 써서

tmp라는걸 만든다.

 

 

 

if row == len(set(tmp)): # 겹치는게 없으니 열이 같다 >> 중복된 값이 없음 # 유일성
    arr.add(i)

유일성 테스트

 

 

 

flag = True
for j in res:
    if set(j).issubset(set(i)): # 겹치는게 있으면
        flag = False
if flag: # 맨 처음 빈 리스트일때 넣음 / 희소성일때 넣음
    res.append(i)

유일성 테스트 통과하면 희소성 테스트