후보키 (Level 2)

문제

 

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

프로그래머스

 

풀이

 

combinations를 사용하여 가능한 인덱스 조합을 모두 구한다.

 

먼저 유일성을 만족하는 키의 집합을 구한다. 문제로 예를 들어 보겠다.

"학번"이 키인 경우 유일성을 만족하기 때문에, 집합 {"100", "200", "300", "400", "500", "600"}의 길이는 relation의 row의 개수와 동일하다. 그러나 "이름"이 키인 경우 유일성을 만족하지 않기 때문에, "ryan", "apeach", "tube", "con", "muzi"}의 길이는 relation의 row 개수보다 적다.

이렇게 set을 사용하여 유일성을 만족하는지 알아본다.

 

유일성이 확인된 조합 com을 기준으로 최소성을 만족하는지 확인한다. unique에 들어있는 원소가 조합 com의 부분집합이라면, 최소성을 만족하지 않는 것이니 put을 False로 설정하고 멈춘다.

 

put이 True인 조합 com에 대해서만 unique에 넣는다.

 

유일성과 최소성 모두를 만족하는 후보키의 개수는 바로 unique의 길이이고, 그것을 반환하면 정답이 된다.

 

from itertools import combinations

def solution(relation):
    
    row = len(relation)
    col = len(relation[0])
    
    combi = []
    for i in range(1, col+1):
        combi.extend(combinations(range(col), i)) # [0, 1, 2, 3 ... col-1]에서 i개 선택하기
    
    unique = []
    for com in combi:
        tmp = [tuple([item[idx] for idx in com]) for item in relation]

        if len(set(tmp)) == row: # 유일성 만족
            put = True
            
            for x in unique:
                if set(x).issubset(set(com)): # 최소성 만족하지 않음
                    put = False
                    break
                    
            if put: unique.append(com)
    
    return len(unique)

 

총평

유일성까지는 풀었는데, 최소성은 머리가 안돌아가서 못 풀었다. 그래서 다른 사람의 풀이를 참고하였다. 이 문제도 나중에 다시 풀어봐야 할 문제다. 레벨 2인데도 못 푸는 문제가 있다는 사실이 너무 슬프다.