[프로그래머스] 후보키

데이터베이스 수업 처음에 배우는 후보키에 대한 설명이 주어지고, 2차원 문자열 배열에서 가능한 후보키의 개수를 찾는 문제이다.

컬럼의 개수가 최대 8개, 로우의 개수가 최대 20개이므로 Brute-Force로 해결할 수 있을 것으로 보고 효율성을 최소한으로 고려하여 문제를 풀었다.

1. 가능한 컬럼 조합을 구한다.
   1.1 from itertool import combinations
2. 각 조합들이 튜플을 식별할 수 있으면 정답 후보로 간주한다.
   2.1 set클래스 또는 dict클래스를 이용한다.
3. 각 후보들 중에서 최소성을 만족하는 컬럼 조합을 찾는다.
   3.1 combinations에서 구한 컬럼 조합은 원소 개수가 1개부터 시작하므로 set클래스의 issubset()메소드를 이용하여 최소성을 확인한다.

진짜 pandas의 n_unique를 사용하고 싶었다.

from itertools import combinations

def solution(relation):
    answer = 0
    
    # STEP 1. 가능한 컬럼 조합을 구한다.
    n_row = len(relation)
    n_col = len(relation[0])
    col_ids = [i for i in range(n_col)]
    attr_combi = {}
    for n_pick in range(1, n_col + 1):
        attrs = combinations(col_ids, n_pick)
        for attr in attrs:
            attr_combi[attr] = {}
    
    # STEP 2. 각 컬럼조합이 튜플을 식별할 수 있으면 후보로 간주한다.
    unique_attrs = []
    for attr in attr_combi.keys():
        items = {}
        for i in range(n_row):
            item = ''
            for j in attr:
                item += relation[i][j]
            items[item] = 1
        if len(items) == n_row: # 튜플식별 여부 파악
            unique_attrs.append(set(attr))
    
    # STEP3. 최소성을 만족하는 컬럼조합만 찾는다.
    candidates = []
    for unique_attr in unique_attrs:
        is_subset = False
        for candidate in candidates:
            if candidate.issubset(unique_attr):
                is_subset = True
                break
        if not is_subset:
            candidates.append(unique_attr)
            
    #print(candidates)
    answer = len(candidates)
    return answer