[프로그래머스] Lv2 - 후보키 (python)

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

프로그래머스

 

접근

유일성을 만족하기 위해 set 자료형을 사용했다. 키의 최대 길이가 8개로, 가능한 키 조합을 모두 구해 각 경우별로 set 자료형으로 변환해도 길이가 변하지 않는 것을 체크했다.

2차원 배열은 set연산을 적용하기가 골치 아파 중간에 한번 tuple 자료형으로 변환해주었다. 

 

유일성을 만족하는 모든 경우의 수를 ck_list 배열에 저장한 뒤, ck_list 배열을 돌면서 최소성을 만족하는지 체크했다.

 

최소성을 만족하는지 체크하기 위해 실제로 최소성을 만족하는 후보키 배열 ck를 만들었다. 모든 후보키에 대해 합집합을 수행해 키가 최소성을 만족하는 경우를 체크했다. (단순히 합집합 한번만 했더니 [(0), (1,2)]과 [1,2,3] 경우를 계산하는 과정에서 0, (1,2,3) 이 조건을 만족하는 것으로 되서 cnt 변수를 통해 모든 후보키에 대해서 고려하도록 수정했다.)

 

한시간정도 걸린 문제였다. 은근 어려워..! 

 

코드

from itertools import combinations

def solution(relation):
    answer = 0
    
    column_list = [i for i in range(len(relation[0]))]

    # 모든 후보키가 될 수 있는 경우의 수(컬럼 인덱스 배열)
    cases = []
    for i in range(1, len(column_list)+1):
        cases.append(list(combinations(column_list, i)))
        
    ck_list = [] 
    for case_list in cases:
        for case in case_list:
            all_senario = []
            for row in range(len(relation)):
                arr = [relation[row][c] for c in case]
                all_senario.append(tuple(arr))
            # print(all_senario)
            
            if len(all_senario) == len(list(set(all_senario))):
                ck_list.append(case)
        
    # print(ck_list)
    
    ck = []
    for key in ck_list:
        if len(ck) == 0:
            ck.append(key)
            continue
        cnt = 0
        for k in ck:
            if set(key) != set(k) | set(key):
                cnt += 1
        
        if cnt == len(ck):
            ck.append(key)
            
    answer = len(ck)        
    return answer

 

 

 

효율성은 없네 경우의 수를 모두 고려해야되서 그런가?