악곱 == 악성곱슬

해시, 순열과 조합

---

해당 문제는 Python으로 풀면 유독 쉽게 풀 수 있는 문제인듯 하다. combinations, issubset 모듈을 사용하여 해결할 수 있다.

해당 문제는 말 그대로 후보키에 대한 정의에 만족하는 집합의 개수를 찾으라는 문제이다. 따라서 집합 원소 개수가 낮은 부분집합부터 차례대로 찾아올라가며 테스트 하면 된다.

구현

---

여기서 2번째 예시의 결과가 5가 나와야 한다. {0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}

{2, 3}은 안된다. 크기가 더 큰 부분집합은 최소성에 위배되어 더이상 찾을 수 없다. 이 경우에 대해서 제대로 고민해 보면 문제를 이해하는데 많은 도움을 얻을 수 있을 것이다.

from itertools import combinations

def solution(relation):
    col, row = len(relation[0]), len(relation)

    index = set(i for i in range(col))
    max_candidate_key = []

    for c in range(1, col + 1):
        for comb in combinations(list(index), c):       # 개수 만큼 뽑는다.
            tmp = set()
            for rel in relation:
                row = tuple(rel[c] for c in comb)       # 해당 열의 인덱스에 해당하는 값을 튜플로 임시 생성한다.
                if row in tmp:                          # 해당 값이 "유일(uniqueness)"하지 않다면
                    break
                tmp.add(row)
            else:
                for key in max_candidate_key:           # 앞선 단계에서 등록된 후보키를 순회하며
                    if set(key).issubset(set(comb)):    # 해당 후보키가 최소성을 만족하는지 체크
                        break
                else:
                    max_candidate_key.append(comb)

    return len(max_candidate_key)

print(solution([["100","ryan","music","2"],
                ["200","apeach","math","2"],
                ["300","tube","computer","3"],
                ["400","con","computer","4"],
                ["500","muzi","music","3"],
                ["600","apeach","music","2"]]
               )) >> 2

print(solution([
    ["a", "b", "c", "d"],
    ["a", "c", "d", "e"],
    ["b", "b", "e", "f"],
    ["c", "d", "c", "d"]
])) >> 5