[프로그래머스/파이썬] 후보키

나의 풀이

from itertools import combinations

def solution(relation):
    col = len(relation[0])
    row = len(relation)
    pool = []
    key = []
    for i in range(1, col + 1):
        pool.extend(sorted(list(combinations(range(col), i))))
    idx = 0
    while idx < len(pool):
        s = set()
        for j in range(row):
            l = list()
            for i in pool[idx]:
                l.append(relation[j][i])
            s.add(tuple(l))
        if len(s) == row:
            key.append(pool[idx])
            x = idx + 1
            while x < len(pool):
                flag = True
                for y in pool[idx]:
                    if y not in pool[x]:
                        flag = False
                        break
                if flag:
                    pool.pop(x)
                else:
                    x += 1
        idx += 1
    return len(key)

 

 

비트연산을 활용한 풀이

def solution(relation):
    answer_list = list()
    for i in range(1, 1 << len(relation[0])):
        tmp_set = set()
        for j in range(len(relation)):
            tmp = ''
            for k in range(len(relation[0])):
                if i & (1 << k):
                    tmp += str(relation[j][k])
            tmp_set.add(tmp)

        if len(tmp_set) == len(relation):
            not_duplicate = True
            for num in answer_list:
                if (num & i) == num:
                    not_duplicate = False
                    break
            if not_duplicate:
                answer_list.append(i)
    return len(answer_list)

 - '1001' + '2' 와 '100' + '12'를 구별하지 못함.\

 - 그러나 여전히 비트연산을 활용하는 아이디어는 좋은듯.

 

 

 

교집합으로 최소성을 확인하는 풀이

from collections import deque
from itertools import combinations
def solution(relation):
    n_row=len(relation)
    n_col=len(relation[0])  #->runtime error 우려되는 부분

    candidates=[]
    for i in range(1,n_col+1):
        candidates.extend(combinations(range(n_col),i))

    final=[]
    for keys in candidates:
        tmp=[tuple([item[key] for key in keys]) for item in relation]
        if len(set(tmp))==n_row:
            final.append(keys)

    answer=set(final[:])
    for i in range(len(final)):
        for j in range(i+1,len(final)):
            if len(final[i])==len(set(final[i]).intersection(set(final[j]))):
                answer.discard(final[j])

    return len(answer)

 - isdisjoint(), issubset(), ussuperset() 등을 활용해도 좋을 듯