[파이썬] 프로그래머스 : 후보키 (Lv.2)

[파이썬] 프로그래머스 : 후보키 (Lv.2)

프로그래머스

 

---

풀이

0. 방향성 생각

1. arr 1개 & 유일성 만족 -> candidates에 인덱스 추가

2. cases에 2개 이상 attribute 결합 추가 3.

유일성 만족 -> 최소성 만족 검사

1. Attribute 1개 & 유일성 만족하는 column 찾기

    n = len(relation)
    columns = list(zip(*relation))
    
    candidates = set()
    for idx,col in enumerate(columns):
        if len(set(col)) == n: # att 1개 & 유일성 만족
            candidates.add((idx,))

 

2.  Attribute 2개 이상인 모든 케이스 찾기

    cases = [] # att 2개 이상
    for i in range(2,len(columns)+1):
        cases.extend(list(C(range(len(columns)),i)))

 

3. 유일성 체크, 최소성 체크

    for case in cases: # 후보키 검사
        if len(set(zip(*[columns[i] for i in case]))) == n: # 유일성 체크
            minimal = True
            for candidate in candidates: # 후보키 참조하는지 확인
                if set(candidate).issubset(set(case)): # 후보키가 case의 부분집합이면 최소성 x
                    minimal = False
                    break
            if minimal:
                candidates.add(case)
                
    return len(candidates)

case에는 인덱스가 들어있다.

columns에서 데이터를 가져오고 전치행렬 zip(*리스트)를 통해서 원소 개수가 relation 수와 같은지 체크

candidate에는 후보키가 들어있다. candidate의 모든 원소가 case의 부분집합이면 안된다.

즉, set(candidate) & set(case) == set(candidate)이면 안된다. 이럴 경우에 최소성 False

 

이후 candidates에 들어있는 원소의 개수를 세주면 된다.

---

전체코드

from itertools import combinations as C

def solution(relation):

    n = len(relation)
    columns = list(zip(*relation))
    
    candidates = set()
    for idx,col in enumerate(columns):
        if len(set(col)) == n: # att 1개 & 유일성 만족
            candidates.add((idx,))
    
    cases = [] # att 2개 이상
    for i in range(2,len(columns)+1):
        cases.extend(list(C(range(len(columns)),i)))

    for case in cases: # 후보키 검사
        if len(set(zip(*[columns[i] for i in case]))) == n: # 유일성 체크
            minimal = True
            for candidate in candidates: # 후보키 참조하는지 확인
                if set(candidate).issubset(set(case)): # 후보키가 case의 부분집합이면 최소성 x
                    minimal = False
                    break
            if minimal:
                candidates.add(case)
                
    return len(candidates)