[프로그래머스] 후보키

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

코딩테스트 연습 - 후보키

 

유일성과 최소성을 만족하는 후보키의 개수를 구하는 문제다.

combinations 을 이용하여 1개부터 열의 개수(len(relation[0])) 까지 조합할 수 있는 경우를 구한 뒤 유일성(len(s) == N)을 확인한다.

 

다음, 길이가 가장 짧은 것부터 candidateKey 에 담으므로 유일성을 만족한 키(= set(j)) 가 candidateKey(= 후보키, j보다 길이가 짧다.) 와 비교해서 이미 선택된 모든 후보키가 j 의 부분집합이 아니라면 j 는 최소성도 만족하므로 후보키로 candidateKey 에 담는다.

 

마지막으로 결정된 candidateKey 의 길이를 반환해주면 된다. 

 

from itertools import combinations

def solution(relation):
    answer = 0
    colNum = [i for i in range(len(relation[0]))]
    N = len(relation)
    candidateKey = []
    
    for i in range(len(colNum)):
        for j in list(combinations(colNum, i+1)):
            s = set()
            
            for row in relation:
                s.add(''.join([row[k] for k in j]))
                
                if len(s) == N:
                    key = True
                    
                    for k in range(len(candidateKey)-1, -1, -1):
                        if len(set(candidateKey[k]) - set(j)) == 0:
                            key = False
                            break
                            
                    if key: candidateKey.append(j)
    
    answer = len(candidateKey)
    
    return answer

print(solution([['100', 'ryan', 'music', '2'], ['200', 'apeach', 'math', '2'], ['300', 'tube', 'computer', '3'], ['400', 'con', 'computer', '4'], ['500', 'muzi', 'music', '3'], ['600', 'apeach', 'music', '2']])) # 2