프로그래머스 - 후보키 (python)

후보키

링크

코딩테스트 연습 - 후보키

[ 문제에 대한 이해 ]

• 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
• 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

접근 방법

우선, 키 들이 유일성과 최소성을 모두 만족시키기 위해서는 완전 탐색을 진행해야 한다. 완전 탐색은 백트래킹으로도 가능하지만, 여기서는 최소성을 만족하는지 쉽게 알아볼 수 있도록, 비트마스킹을 활용하여 완탐색을 시도하였다.

for i in range(1, 1 << len(relation[0])):
    pass

만약 4개의 키가 있다면 1이라면 0001, 5이라면 0101이 된다. 이 말은 배열에서 0번째 인덱스와 2번째 인덱스를 키로 사용하겠다는 뜻과 같다.

우선 유일성을 만족하는 경우에 대해 알아보자. relation의 모든 튜플은 유일하게 식별이 가능하므로, 모든 키의 값들을 string으로 저장하고 난 뒤, 해당 값을 집합 자료구조를 사용하여 배열의 길이와 집합 자료구조의 길이가 다르다면 유일성을 만족하지 않는다는 뜻과 동일하다.

def is_unique_array(arr):
    return len(arr) == len(list(set(arr)))

해당 키를 이용하여 탐색하기 전에, 해당 키가 최소성을 만족하는 지 확인한 뒤, 최소성을 만족하지 않는 다면 해당 키에 대하여 탐색하지 않도록 한다면 시간을 절약할 수 있다.

def is_key_minimal(arr, key):
    for k in arr:
        if (k & key) == k:
            return False
    return True

if not is_key_minimal(keys, i):
    continue

통과 코드

    def is_key_minimal(arr, key):
        for k in arr:
            if (k & key) == k:
                return False
        return True
    
    def is_unique_array(arr):
        return len(arr) == len(list(set(arr)))
    
    def solution(relation):
        keys = []
        for i in range(1, 1 << len(relation[0])):
            arr = []
    
            # TODO: Check if i satisfies minimality
            if not is_key_minimal(keys, i):
                continue
    
            for j in range(len(relation)):
                temp = ""
    
                for k in range(len(relation[0])):
                    if not (i & 1 << k):
                        continue
    
                    temp += relation[j][k]
    
                arr.append(temp)
    
            if is_unique_array(arr):
                keys.append(i)
    
        return len(keys)
    
    relation = [
        ["100", "ryan", "music", "2"],
        ["200", "apeach", "math", "2"],
        ["300", "tube", "computer", "3"],
        ["400", "con", "computer", "4"],
        ["500", "muzi", "music", "3"],
        ["600", "apeach", "music", "2"],
    ]
    
    print(solution(relation))