[ Lv 2 ] 후보키

풀이 과정

---

• row와 column의 범위가 작은 편이므로 combinations를 사용하여서 풀이

1. 모든 column의 조합들을 구한다. (1개 ~ column의 길이)
2. 각각의 column 조합에 대해 최소성과 유일성 검사
   • 최소성의 경우는, 각 column의 조합에 대해 다시 조합들을 구한 뒤, 조합들중 하나라도 후보키에 있는지 검사
   • 유일성의 경우는, 릴레이션에서 각 튜플들에 대해 column의 조합으로 데이터를 구성하여 하나씩 넣어본 다음, 중복되는 요소가 있다면 유일성 만족하지 않음.
3. 후보키의 개수를 리턴해주면 된다.

---

소스 코드

---

from itertools import combinations

# 유일성 만족 확인
def simulation(relation, columns):
    compare_set = set()
    for tup in relation:
        target = []
        for col in columns:
            target.append(tup[col])
        target = tuple(target)
        if target in compare_set:
            return False
        compare_set.add(target)
    return True

# 최소성 확인(자신보다 짧은 최소키가 있는지)
def check_in_set(candidate, case):
    case_len = len(case)

    for i in range(1, case_len+1):
        total_case = list(combinations(case, i))
        for case_ in total_case:
            if case_ in candidate:
                return False
    return True


def solution(relation):
    answer = 0
    col_len = len(relation[0])
    cols = [i for i in range(col_len)]
    candidate = set()
    for i in range(1, col_len+1):
        all_case = list(combinations(cols, i))
        for case in all_case:
            # 유일성과 최소성을 만족하는지 확인
            if check_in_set(candidate, case) and simulation(relation, case): 
                candidate.add(case)
                answer += 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges