[프로그래머스] Level2 후보키(python)

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

프로그래머스

 

 

1. 문제 해결 방법

 

for문 진행 중, 최소성을 만족시키는 걸 지웠더니 단단히 꼬여서 5시간은 걸린 듯 하다.

 

그래도 끝까지 풀었다는 것에 만족

 

 

내 코드는 너무 비효율적이라,, 일단 블로그 포스팅 해놓고 다음에 리팩토링하러 와야겠다 

 

지금은 힘이 하나도 업삼ㅁ,,,

 

from itertools import combinations

def solution(relation):
    coms = []
    attributes = [i for i in range(len(relation[0]))] #전체 속성 값
    
    for i in range(1,len(relation[0])+1): #가능한 전체 조합을 str로 만들기
        for co in combinations(attributes,i):
            part = ""
            for j in co:
                part += str(j)
            coms.append(part)
    
    candidate = []
    dele = set()
    
    for co in coms: #유일성 만족하는지 확인
        if check(co,relation):
            candidate.append(co)
    
    for co in candidate: #최소성 만족하는지 확인
        for ck in candidate:
            if len(ck) > len(co) and removes(co,ck):
                dele.add(ck)
    
    for i in dele: #유일성을 만족한 후보키 중 최소성에 위배되면 삭제
        candidate.remove(i)
          
    return len(candidate)
    

def removes(co,ck): #최소성 확인
    num = 0
    for i in co:
        if i in ck:
            num += 1
    if num == len(co): return True
    

def check(coms,relation): #유일성 확인
    dic = {}
    for i in range(len(relation)):
        part = ""
        for j in coms:
            part += str(relation[i][int(j)])
        dic[part] = 0
    if len(dic.keys()) == len(relation):
        return True

 

미래의 나를 위한 메모

 

유일성 : 딕셔너리에 키값으로 다 저장했을 경우 key값의 길이와 전체 튜플의 개수가 맞으면 유일성인 것을 확인

 

최소성 : 유일성을 통과한 애들의 전체 집합이 포함되었으면 최소성을 위배한 것이니까 False 반환

 

set(x).issubsut(u_total) => x가 u_total의 부분집합인지 알 수 있음