프로그래머스 2단계 - 후보키 (Python)

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

코딩테스트 연습 - 후보키

 

참고 블로그:

https://whwl.tistory.com/104

[프로그래머스] 후보키 /파이썬 /Python /2019 KAKAO BLIND RECRUITMENT /카카오 코테

 

알아둬야할 키포인트는 유일성과 최소성이다.

1. 유일성: 릴레이션에 있는 모든 튜플이 유일하게 실별된다. (ex: 학번)

2. 최소성: 릴레이션의 모든 튜플을 유일하게 식별하는 데에 꼭 필요한 속성들로만 구성돼야한다.

   (ex: (학번, 이름)으로도 모든 튜플들을 식별 가능하지만 학번만으로도 가능하기 때문에 (학번, 이름)은 최소성을 만족시키지 못한다.)

 

알고리즘:

1. 조합을 이용해서 열 (학번, 이름, 전공, 학년) 에서의 모든 조합을 알아낸다. ((학번), (이름), ..., (학번, 이름), ....)

2. 만약 중복을 제거했는데 원본과 길이가 같다면 유일성을 만족하는 것으로 간주한다. 유일성을 만족하는 것은 final 배열에 담는다.

(이름에서 중복을 제거하면 ryan, apeach, tube, con, muzi로 길이가 5이 되고 원래 길이는 6이였기 때문에 유일성을 만족하지 못한다고 할 수 있다.)

3. 최소성은 교집합을 이용한다. final 배열의 모든 두 원소를 한번씩 비교해서 교집합을 구한다. 예를 들어, 앞선 과정에서 final 배열에는 ((학번), ..., (학번, 이름), ...) 의 순서대로 저장돼있는데, (학번)과 (학번, 이름)의 교집합을 구하면 (학번)이 나오기 때문에 (학번, 이름)을 제거해주면 된다.

 

이용한 파이썬 스킬들:

1. set함수는 배열 안에서 중복을 제거해준다.

2. intersection 함수는 교집합을 구해준다. set(배열1).intersection(set(배열2))로 사용하거나 set(배열1) & set(배열2)로 사용할 수도 있다.

 

 

from itertools import combinations
 
def solution(relation):
    answer = 0
    rows = len(relation)
    cols = len(relation[0])
    
    #유일성
    candidates = []
    for i in range(1, cols+1):
        candidates.extend(combinations(range(cols), i)) #(0), (1), ... 이렇게 인덱스들이 들어가있다. 0~3까지 모든 조합을 알아내겠다는 뜻이다.
    
    final = []
    for c in candidates:
        tmp = [tuple(item[key] for key in c) for item in relation] #인덱스를 객체로 만들어준다.
        if len(set(tmp)) == rows: #모든 조합을 만들어준 tmp에서 중복을 제거한게 원래 행 길이와 같을 경우
            final.append(c)
    
    answer = set(final) #set으로 만들어줘야 나중에 discard가 가능하다.
    
    #최소성
    #set으로 해주고 순회하면 사전순대로 순회하게 된다는걸 기억해야한다.
    for i in range(len(final)):
        for j in range(i+1, len(final)):
            if len(final[i]) == len(set(final[i]).intersection(set(final[j]))):
                answer.discard(final[j])
 
    return len(answer)