[Python] 2019 KAKAO BLIND RECRUITMENT - 후보키

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

코딩테스트 연습 - 후보키

[ 알고리즘 ]

구현

 

[문제 접근]

최소성을 어떻게 접근해야할지 몰라서 고민하다가 다른 분의 블로그를 참고해서 풀이한 문제

조합과 set을 이용하여 구하는 문제라고는 처음에도 생각해서 풀었는데, set의 교집합을 이용하여 구한다는 생각까지는 못했던 것 같다.

 

* 그래도 이 코드를 풀이하며 얻는 점이 몇가지가 있다.

 

1) 해시가능(Hashable) 의 의미와 불변성(Immutability)
https://yeon-woo-kim.tistory.com/category/etc

- set을 구해줄 때 리스트는 가변형이기 때문에 tuple을 사용해줘야한다는 점을 배웠다

 

2) 매번 append만 사용했었는데, extend 를 이용하면 iterable한 객체를 추가할 수 있다는 점도 배웠다

 

3) remove 대신 discard를 사용할시에, 삭제 할 원소가 존재하지 않아도 오류가 나지 않는다는 점을 배웠다. 앞으로remove보단 discard를 애용하게 될 것 같음

 

[코드]

from itertools import combinations

def solution(relation):
    answer=0
    
    n=len(relation) #  학생의 수
    m=len(relation[0]) # 후보키의 개수
    
    #전체 조합
    combination=[]
    for i in range(1,m+1):
        combination.extend(combinations(range(m),i))
        
    
    #유일성
    unique=[]
    for com in combination:
        tmp=[tuple([List[i] for i in com]) for List in relation]
        
        if len(tmp)==len(set(tmp)):
            unique.append(com)

    
    #최소성
    answer=set(unique)
    
    for i in range(len(unique)):
        for j in range(i+1,len(unique)):
            if len(unique[i]) == len(set(unique[i])&set(unique[j])):
                answer.discard(unique[j])
                  

    return len(answer)