250408_프로그래머스 #42890. 후보키

문제

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

프로그래머스

---

코드

from itertools import combinations

def solution(relation):

    row = len(relation)
    col = len(relation[0])
   
    combs = []
    for i in range(1, col + 1):
        combs.extend(combinations(range(col), i))
    
    # 유일성
    unique = []
    for comb in combs:
        tmp = [tuple([item[i] for i in comb]) for item in relation]
        if len(set(tmp)) == row:
            unique.append(comb)
            
    # 최소성
    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)

 

※ 조합까지는 생각했는데, 유일성과 최소성을 확인하는 로직 구현이 어려웠다. 결국 검색으로 해결 ..ㅎ 은근 이해하는데 오래걸렸는데 우선 유일성은, 조합된 속성들만 tmp에 담아서 확인하는 방식 ! 예를 들어, tmp = [("어피치", "computer"), ("콘", "music"), ("어피치", "computer")] 이렇게 담기는데 set을 씌웠을 때 길이가 줄어들면 중복이 있는거라 유일성을 만족하지 않는다. 그리고 최소성은, 유일성을 만족한 키들과의 비교인데 ! 예를 들어, {1, 2} {1, 2, 3}이라는 후보키가 있을 때 {1, 2} & {1, 2, 3} = {1, 2}이기 때문에 이런 식으로 두 후보키 사이에 포함관계가 생긴다면 최소성을 만족하지 않는다.

 

확실히 쓰면서 로직 정리가 되는 느낌이군.. 쨌든 얘는 나중에 다시 함 봐야겠다 ^ 다른 분은 비트 연산이나 issubset을 쓰는 것도 봤는데 ! 나는 그나마 이 코드가 가장 직관적으로 이해됐음 ~