프로그래머스 문제 후보키

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

프로그래머스

 

카카오 코딩테스트의 문제 특성상 Level2의 문제는 탐색 공간이 크지 않아 완전탐색으로 간단하게 해결이 가능하지만 세부적인 구현사항에서는 나름 시간을 요구하는 구현사항이 필요하다.

* combination으로 모든 column의 조합을 구하기

* set을 이용해서 unique한 특성을 가졌는지 체크하기

* 이미 구해진 후보키들과 비교해서 minimality한지 체크하기

 

from itertools import combinations
def check_minimality(candidate_key, comb):

    # 이미 조건을 만족한 후보키 전부와 비교해서 곂치는 값이 있으면 False 없으면 True
    for key in candidate_key:
        tmp_count = 0
        for column in key:
            if column in comb:
                tmp_count +=1
        if tmp_count == len(key):
            return False
    return True

def solution(relation):

    # column의 개수
    num = len(relation[0])

    # 1개 부터 column의 최대개수까지 모든 조합을 구해서 넣어줌
    all_combs = []
    for i in range(1, num+1):
        tmp = list(combinations(range(num),i))
        all_combs.extend(tmp)

    # 결과 저장과 minimality를 확인하기 위한 list
    result = []

    for comb in all_combs:
        tmp_set = set()

        # 각각의 column 조합별로 직접 set에 넣어줌, 중복되는 row는 자동 삭제
        for row in relation:
            uniqueness = []
            for idx in comb:
                uniqueness.append(row[idx])
            tmp_set.add(tuple(uniqueness))

        # set의 길이와 row의 길이가 같다면 unique 하다고 판단
        if len(tmp_set) == len(relation):

            # minimality도 만족하면 최종결과에 저장
            if check_minimality(result, comb): result.append(comb)

    return len(result)