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

문제풀이

1.  조합 함수(combination)을 활용하여 가능한 인덱스 조합을 만든다.

2.  각 행에서 1에서 뽑은 인덱스에 해당하는 값들만 추출하여 중복값이 없는지 찾는다. => 유일성

  (set에 넣어서 요소의 수를 총 행의 수와 비교한다.)

3.  각 단계에서 추출된 익덱스 집합이 이전에 선택된 인덱스 집합의 부분집합이 되는 경우는 없는지 확인한다. => 최소성

  (combination을 통해 추출한 조합의 인덱스 개수는 1부터 늘어남으로 이전에 선택된 인덱스 조합만 확인하면 된다.)

 

Python Code

from itertools import combinations
 
def solution(relation):
    rows = len(relation)
    cols = len(relation[0])
    keys = []
    
    for n in range(1,cols+1):
        for idxs in combinations(range(cols),n):
            # 최소성 and 유일성
            if min_check(keys,idxs) and \
                    len(set(tuple(relation[row][idx] for idx in idxs) for row in range(rows))) == rows :
                keys.append(idxs)
    
    return len(keys)
 
#최소성
def min_check(keys, target):
    for k in keys:
        if set(k).issubset(set(target)):
            return False
    return True

문제 링크

코딩테스트 연습 - 후보키