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

💁🏻 나의 풀이

from itertools import combinations

def is_unique(rel, c):
    unique = set()
    for row in rel:
        arr = []
        for i in c:
            arr.append(row[i])
        unique.add(tuple(arr))
    return len(rel) == len(unique)

def solution(relation):
    answer = 0
    column_cnt = len(relation[0])
    comb = []

    for i in range(1, column_cnt + 1):
        comb.extend(combinations(range(column_cnt), i))

    unique_comb = []
    for c in comb:
        if is_unique(relation, c):
            unique_comb.append(c)

    min_check = [1] * len(unique_comb)
    for i in range(len(unique_comb)):
        for j in range(i+1, len(unique_comb)):
            if min_check[j] == 0:
                continue
            elif set(unique_comb[i]).issubset(set(unique_comb[j])):
                min_check[j] = 0

    return sum(min_check)

👀 다른 사람 풀이

🔗 https://velog.io/@sem/프로그래머스-LEVEL2-후보키-Python

from itertools import combinations

def solution(relation):
    row = len(relation)
    col = len(relation[0])

    #가능한 속성의 모든 인덱스 조합 
    combi = []
    for i in range(1, col+1):
        combi.extend(combinations(range(col), i))

    #유일성
    unique = []
    for i in combi:
        tmp = [tuple([item[key] for key in i]) for item in relation]

        if len(set(tmp)) == row:    # 유일성
            put = True

            for x in unique:
                if set(x).issubset(set(i)):  # 최소성
                    put = False
                    break

            if put: unique.append(i)

    return len(unique)

• combinations로 가능한 모든 키 조합을 먼저 생성
• 모든 row에 대해 키 조합 튜플을 선택해서 list로 만든다
• 만든 list을 set으로 중복을 삭제하고 원래 길이와 비교해 유일성을 체크
• 유일성이 검증된 키 조합에 대해 다른 조합들의 부분집합인지 set.issubset 을 활용해 최소성 체크