문제 링크

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

문제 설명

• 후보키의 개수 리턴
  • 후보키 : 유일성, 최소성을 만족하는 컬럼 조합

풀이

• 부분 집합을 모두 구함
• 최소성과 유일성을 모두 만족할 경우 set에 add
  • 최소성 체크
    • 부분 집합의 부분 집합이 이미 set에 존재하면 최소성 X
  • 유일성 체크
    • 중복 값이 있는지 체크
• set의 크기를 리턴

코드

from itertools import combinations


def solution(relation):
    candidates = set()
    cols = len(relation[0])
    for i in range(1, cols + 1):
        for combi in combinations(range(cols), i):
            if possible(relation, candidates, combi):
                candidates.add(combi)
    return len(candidates)


def possible(relation, candidates, combi):
    # 최소성
    for i in range(1, len(combi) + 1):
        for combi2 in combinations(combi, i):
            if combi2 in candidates:
                return False
    # 유일성
    unique = set()
    for line in relation:
        curr = []
        for i in combi:
            curr.append(line[i])
        if tuple(curr) in unique:
            return False
        unique.add(tuple(curr))
    return True