[프로그래머스] 후보키 (Python)

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

코딩테스트 연습 - 후보키

 

꽤나 애를 먹었던 문제였다.

 

내가 풀었던 알고리즘은

1. 속성의 개수를 카운트하고 속성을 조합

2. 각 속성으로 유일성을 만족하는지 확인

3. 현재 조합한 속성이 기존에 조합했던 속성과 겹치는 것이 있는지 다시 조합 후 확인(최소성 만족하는지 확인)

 

from itertools import combinations
from collections import defaultdict
def check_combination(answer,cases):
    for a in answer:
        case = ''.join(cases)
        for c in combinations(case,len(a)):
            if a in ''.join(c):
                return False
    return True

def solution(relation):
    attribute_count = len(relation[0])
    tuple_count = len(relation)
    attribute = [str(i) for i in range(attribute_count)]
    dict = defaultdict(set)
    answer = []
    for i in range(1,attribute_count+1):
        for cases in combinations(attribute,i):
            if check_combination(answer,cases):
                for row in relation:
                    unique = ''
                    for idx in cases:
                        unique+=row[int(idx)]
                    dict[cases].add(unique)
                if len(dict[cases]) == tuple_count:
                    answer.append(''.join(cases))
    return len(answer)