[알고리즘] 후보키

포인트

• 생각보다 조합을 사용하는 일이 많다. 
• 후보 키 set 과 검증 set 을 두 개를 정의하여 검증 set을 통과하면 후보 키 set에 넣어주는 방식으로 처리하였다. 
• 또한, 다음 후보 키 중 본인이 가지고 있는 키의 최소 집합을 포함하고 있다면 배제할 수 있도록 전처리를 진행했다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

from itertools import combinations


def solution(relation: list) -> int:
    n = len((relation[0]))
    count = []
    for i in range(1, n + 1):
        count.extend(list(combinations(range(n), i)))

    mapper = set()
    for col in count:
        validation = set()

        for can in mapper:
            # 후보키 맵에서 튜플 들 중
            cnt = 0
            for ele in can:
                # 비교하는 튜플에 원소가 있으면 숫자를 증가시키는데
                if ele in list(col):
                    cnt += 1
            if cnt >= len(can):
                # 만약 원소를 포함시키고 있으면 다음으로
                break
        else:
            for row in range(len(relation)):
                # 데이터를 행으로 이동을 하면서 비교
                temp = []
                for ele in col:
                    temp.append(relation[row][ele])
                # 데이터를 가지고 온뒤
                if tuple(temp) in validation:
                    # 검증 셋에 넣어 검증
                    break
                else:
                    # 검증 셋에 없으면 추가
                    validation.add(tuple(temp))
            else:
                # 후보키 맵에 등록
                mapper.add(col)

    return len(mapper)