[프로그래머스] 2019 카카오 블라인드 #3 후보키

- 블로그 찾아보면 비트마스킹으로 풀었다고 하는데 그게 더 효율적일지도 모르겠다.

- 본인은 set() 자료형과 배열, 부분집합 subset()을 활용하여 풀었다.

- 3중 for문이라니... ㅠㅠ;;; ;; (비공개를..해야하나..) 

- 문제를 이해하는게 어려웠다. 특히 최소성 부분에서 subset()의 개념을 생각하지 못하고 중복하는 건 다 걸러버리도록 로직을 짜서 처음부터 뜯어고쳐야 했다.

- 시간이 굉장히 오래 걸렸지만.. 그래도 혼자 힘으로 구현하긴 했다. 실전이었으면 곤란했을 듯 하다.

from itertools import combinations

def is_duplicate(columns, relation):
    """
    columns 가 (1, 2)라면
    1번과 2번을 합친 값을 구하고 중복확인
    """
    # 튜플 자료형 columns
    new_set = set()
    
    # 모든 tuple 돌면서 해당 column 의 문자열을 더해 set 에 있는지 확인
    for tupl in relation:
        candidate_str = ''
        for column in columns:
            candidate_str += tupl[column]
    
        if candidate_str in new_set:
            return True
        else:
            new_set.add(candidate_str)

    return False
    


def solution(relation):
    # 후보키의 수 
    answer = 0
    
    attr_num = len(relation[0])
    tuple_num = len(relation)
    
    # 후보키면 해당 튜플을 False로 변경
    is_candidate = [True] * attr_num
    
    # 후보키 
    keys = list()
    
    # k 개(1~튜플 갯수)의 튜플 뽑기
    for k in range(1, attr_num + 1):
        maybe_candidate_keys = list(combinations([x for x in range(attr_num)], k))

        for maybe_candidate_key in maybe_candidate_keys:
            flag = True
            if not is_duplicate(maybe_candidate_key, relation): # 유일성 인정        
                maybe_candidate_key = set(maybe_candidate_key)

                if len(keys):
                    for key in keys: # 0   # subset 이면 pass (최소성 미인정)
                        if key.issubset(maybe_candidate_key):
                            flag = False
                            break
                    
                if flag:
                    keys.append(maybe_candidate_key)
                    answer += 1 # 후보키 갯수 + 1
                        
    return answer