[Progrmmers] 후보키

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

프로그래머스

 

내 풀이

# 후보키의 갯수 찾기
from itertools import product

def solution(relation):
    answer = 0
    relations = [1, 0]
    uniques = []
    
    # 유일성 만족하는 값 찾기
    for case in product(relations, repeat=len(relation[0])):
        case = list(case)

        tuples = set()
        for val in relation:
            key = ""
            for idx,c in enumerate(case):
                if c == 1:
                    key += '+'+val[idx]
            tuples.add(key)
        if len(tuples) == len(relation): # 유일성 만족 
            answer += 1
            uniques.append(case)
        
    indexes = []
    for unique in uniques:
        tmp = []
        for i in range(len(unique)):
            if unique[i] == 1:
                tmp.append(i)
        indexes.append(tmp)
    
    def isIncluded(lis1, lis2):
        count = 0
        for i in lis1:
            if i in lis2:
                count += 1
        if count == len(lis1):
            return True
        else:
            return False
    
    # 최소성 만족하는 값 찾기
    indexes.sort(key = lambda x:len(x))
    deleted = [False]*len(indexes)
    for i in range(len(indexes)):
        for j in range(i+1, len(indexes)):
            if len(indexes[i]) == 0 or len(indexes[j]) == 0:
                continue
            if isIncluded(indexes[i], indexes[j]) and (not deleted[j]):
                deleted[j] = True
                answer -= 1   
    
    return answer

 

코드가 좀 길지만 혼자 힘으로 풀었다는 것에 의의를 !

 

itertools 라이브러리의 product로 중복순열을 구해준다.

1001 이런식으로 1은 키로 사용하는 칼럼, 0은 키로 사용하지 않는 칼럼

set 자료형으로 유일성을 만족하는 것들의 집합을 구해주고

최소성을 만족하지 않으면 삭제해준다.

 

실수 하나로 시간이 좀 오래 걸렸는데, 만약 [1, 3], [1, 2, 3] 이럴 때 오른쪽은 삭제되어야 한다. 하지만 둘이 비교하는 과정에서 더 짧은 길이만큼 반복문을 돌려서 같은 숫자의 갯수가 짧은 리스트의 길이와 같을 때 삭제하는 로직을 짰던 것.

 

 

😎 그냥 구글링 하면서 추가적으로 배운 것

set issubset() , issuperset()

 

해당 set이 다른 set의 부분 set인지 확인할 수 있는 것이다. 근데 이번 풀이엔 set에 여러 리스트가 있고 각각 리스트가 상위 set인지 확인해야 했어서 적용하진 못했다.

product 배워서 유용하게 써먹은 것 처럼 이것도 잘 익혀두자.