1. 문제 설명

후보키

2. 문제 분석

후보키가 될 수 있는 어트리뷰트(칼럼)의 경우의 수를 미리 구한다. 각 경우의 수에 따라 튜플을 확인하며 중복된 튜플이 있을 경우 프라이머리 키 조건을 위배하므로 False, 중복되지 않았을 경우에 후보키가 될 수 있다. 이때 이 후보키의 부분 집합이 이미 후보키인 경우는 제외해야 한다(훨씬 더 적은 경우의 수로 조합했을 때에도 후보키로 적용할 수 있기 때문이다).

3. 나의 풀이

1.

from itertools import combinations
def solution(relation):
    col_num = len(relation[0])
    key_range = list(range(col_num))
    candidate_keys = []
    combs = []

    for i in range(1, col_num+1):
        combs += combinations(key_range, i)

    for comb in combs:
        checks = []
        check = True
        for record in relation:
            rec = [record[i] for i in comb]
            if rec not in checks: checks.append(rec)
            else:
                check= False
                break
        if check:
            minimal = True
            for candidate_key in candidate_keys:
                if set(comb).issuperset(candidate_key):
                    minimal = False
                    break
            if minimal: candidate_keys.append(comb)
    return len(candidate_keys)

• 중복 확인 이후 기존 후보키와의 포함 관계를 확인한 뒤 후보키에 추가한다. 이때 집합 함수 issuperset 또는 issubset을 통해 손쉽게 포함 관계를 확인할 수 있다. 하지만 이 경우 불필요한 후보키를 계속해서 구하게 된다는 단점이 있었다. 즉 '0'번 칼럼을 통해 후보키가 결정되었으면, 다음부터 찾을 후보키 리스트에 들어가는 경우의 수 조합에는 '0'번이 있을 필요가 없다. 후보키가 확정된 경우 경우의 수 조합 자체에서 그 경우의 수를 제외한다면 보다 빨리 구할 수 있을 것이다.

테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.03ms, 10.4MB)
테스트 3 〉	통과 (0.05ms, 10.2MB)
테스트 4 〉	통과 (0.05ms, 10.2MB)
테스트 5 〉	통과 (0.04ms, 10.3MB)
테스트 6 〉	통과 (0.01ms, 10.2MB)
테스트 7 〉	통과 (0.01ms, 10.3MB)
테스트 8 〉	통과 (0.01ms, 10.3MB)
테스트 9 〉	통과 (0.08ms, 10.2MB)
테스트 10 〉	통과 (0.14ms, 10.3MB)
테스트 11 〉	통과 (0.24ms, 10.3MB)
테스트 12 〉	통과 (0.64ms, 10.3MB)
테스트 13 〉	통과 (0.22ms, 10.2MB)
테스트 14 〉	통과 (0.05ms, 10.3MB)
테스트 15 〉	통과 (0.03ms, 10.2MB)
테스트 16 〉	통과 (0.04ms, 10.3MB)
테스트 17 〉	통과 (0.07ms, 10.2MB)
테스트 18 〉	통과 (2.96ms, 10.3MB)
테스트 19 〉	통과 (1.21ms, 10.3MB)
테스트 20 〉	통과 (2.76ms, 10.3MB)
테스트 21 〉	통과 (1.02ms, 10.4MB)
테스트 22 〉	통과 (0.54ms, 10.3MB)
테스트 23 〉	통과 (0.06ms, 10.3MB)
테스트 24 〉	통과 (1.80ms, 10.3MB)
테스트 25 〉	통과 (2.78ms, 10.3MB)
테스트 26 〉	통과 (1.43ms, 10.3MB)
테스트 27 〉	통과 (0.27ms, 10.3MB)
테스트 28 〉	통과 (0.30ms, 10.3MB)

2.

from itertools import combinations
def solution(relation):
    col_num = len(relation[0])
    key_range = list(range(col_num))
    candidate_keys = []
    combs = []

    for i in range(1, col_num+1):
        combs += combinations(key_range, i)

    while combs:
        for comb in combs:
            checks = []
            check = True
            for record in relation:
                rec = [record[i] for i in comb]
                if rec not in checks: checks.append(rec)
                else:
                    check= False
                    break
            if check:
                cur_comb = comb
                candidate_keys.append(cur_comb)
                new_combs = []
                for comb in combs:
                    if not set(cur_comb).issubset(set(comb)):
                        new_combs.append(comb)
                combs = new_combs
                break
            else:
                combs.remove(comb)
                break
    return len(candidate_keys)

• 새로운 combs(경우의 수 조합을 담은 리스트)를 구해 후보키를 확인하는 연산의 수를 줄였다. 이때 check=False, 즉 본 조합이 후보키 조합이 될 수 없다면 전체 경우의 수에서 제거해주어야 하는데, 그렇지 않으면 끝까지 while 문을 탈출할 수 없다. 다소 복잡한 케이스이지만 시간을 줄일 수 있었다.

테스트 1 〉	통과 (0.04ms, 10.3MB)
테스트 2 〉	통과 (0.03ms, 10.3MB)
테스트 3 〉	통과 (0.03ms, 10.3MB)
테스트 4 〉	통과 (0.04ms, 10.2MB)
테스트 5 〉	통과 (0.05ms, 10.3MB)
테스트 6 〉	통과 (0.01ms, 10.3MB)
테스트 7 〉	통과 (0.01ms, 10.3MB)
테스트 8 〉	통과 (0.02ms, 10.3MB)
테스트 9 〉	통과 (0.11ms, 10.3MB)
테스트 10 〉	통과 (0.04ms, 10.3MB)
테스트 11 〉	통과 (0.08ms, 10.4MB)
테스트 12 〉	통과 (0.24ms, 10.3MB)
테스트 13 〉	통과 (0.16ms, 10.4MB)
테스트 14 〉	통과 (0.04ms, 10.3MB)
테스트 15 〉	통과 (0.03ms, 10.3MB)
테스트 16 〉	통과 (0.05ms, 10.3MB)
테스트 17 〉	통과 (0.04ms, 10.2MB)
테스트 18 〉	통과 (0.63ms, 10.3MB)
테스트 19 〉	통과 (0.62ms, 10.2MB)
테스트 20 〉	통과 (1.51ms, 10.2MB)
테스트 21 〉	통과 (1.07ms, 10.2MB)
테스트 22 〉	통과 (1.27ms, 10.4MB)
테스트 23 〉	통과 (0.04ms, 10.3MB)
테스트 24 〉	통과 (0.71ms, 10.4MB)
테스트 25 〉	통과 (1.34ms, 10.3MB)
테스트 26 〉	통과 (0.65ms, 10.3MB)
테스트 27 〉	통과 (0.09ms, 10.2MB)
테스트 28 〉	통과 (0.15ms, 10.3MB)