[programmers/py] 후보키

후보키

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

문제 설명

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

후보키
유일성과 최소성을 만족하는 키

풀이

유일성을 만족하는 경우와 최소성을 만족하는 경우로 구분해서 문제를 푼다.

유일성은 뜻 그대로 각 열의 행의 수가 다 다른 경우를 말해 배열의 길이를 활용해 값을 구할 수 있다.

최소성은 부분집합을 이용해 현재 유일성을 만족하는 집합이 다른 집합에 포함되어 있다면 다른 집합을 제거해 최소성을 유지

from itertools import combinations

def solution(relation):
    answer = []    
    col = len(relation[0])
    row = len(relation)
       
    for i in range(1, col+1):
        candis = list(combinations(range(col), i))
                
        for candi in candis:
            tuples = [] # 후보키 조합들 
            
            for r in relation:
                t = []
                for c in candi:
                    t.append(r[c])
                
                if t not in tuples:
                    tuples.append(t)
            
            if len(tuples) == row: # 유일성을 만족하는 경우
                answer.append(set(candi))
    
    l_a = len(answer)
    a2 = answer.copy()
    for i in range(l_a): # 최소성 만족
        for j in range(i+1, l_a):
            k1 = answer[i]
            k2 = answer[j]
            if k1.issubset(k2):
                try:
                    a2.remove(k2)
                except:
                    continue
    return len(a2)

후기

유일성 같은 경우는 쉽게 풀 수 있었지만, 최소성을 만족하는 경우에 대해서는 다른 사람의 풀이를 보고 이해