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

mog·2020년 12월 13일
2

프로그래머스 level2. 후보키

👀 문제 풀이 아이디어

👀 전체 코드

from collections import deque
from itertools import combinations

def solution(relation):
    n = len(relation)
    m = len(relation[0])
    answer = 0

    # 가능한 모든 조합 구하기
    com = []
    for i in range(1,m+1):
        com.extend(list(combinations(range(m), i)))
    
    # 유일성 만족하는 키 찾기
    keys = deque()
    for i in com:
        temp = ['' for _ in range(n)]
        for idx1, j in enumerate(i):
            for idx2,k in enumerate(relation):
                temp[idx2] += k[j]
        if len(set(temp)) == n:
            keys.append(i)
            
    # 최소성 만족하는 키 찾기 
    while keys:
        temp = keys.popleft()
        answer += 1
        new = deque()
        for i in keys:
            if len(set(i)-set(temp)) != len(i)-len(temp):
                new.append(i)
        keys = new
    return answer

0개의 댓글