[2019 KAKAO BR] 후보키

후보키

• 후보키는 유일성과 최소성을 만족하는 속성의 집합
• 1 <= row 개수 <= 20
• 1 <= column 개수 <= 8
• 후보키의 최대 개수를 구해서 리턴

Solution

• 행렬을 전치시켜서 column 별로 데이터를 가져오기 쉽게
• 각 column을 0 ~ C-1 의 index로 나타내기
• column에서 n(1부터 C)개의 조합을 선택 했을때, 선택된 column들이 최소성과 유일성을 만족하는지 검사
• 최소성 : 후보키로 결정된 조합을 포함하는 조합은 최소성 만족하지 않음
• 유일성 : 선택된 column 들의 문자열을 join한 문자열로 유일성 검사

Code

from itertools import combinations

# 최소성 검사
def not_minimal(comb,possibles):
    for possible in possibles:
        if possible & comb == possible : return True
    return False

# 유일성 검사
def not_unique(comb, cols, R):
    tmp_col = [[] for _ in range(R)]
    for i in comb:
        for j in range(R):
            tmp_col[j].append(cols[i][j])
    tmp_col = [''.join(row) for row in tmp_col]
    return R > len(set(tmp_col))

def solution(relation):
    R, C = len(relation), len(relation[0])
    cols = [[ relation[i][j] for i in range(R)] for j in range(C)]
    elements = [i for i in range(C)]
    possibles = []

    for r in range(1,C+1):
        for comb in combinations(elements,r):
            comb=set(comb)
            if not_minimal(comb, possibles) : continue
            if not_unique(comb, cols, R): continue
            possibles.append(comb)

    return len(possibles)

`