[알고리즘] 프로그래머스 - 후보키

프로그래머스 - 후보키

내 풀이

from itertools import combinations

def is_minimum(key_comb, candidate_keys):
    for candidate_key in candidate_keys:
        if set(candidate_key).intersection(set(key_comb)) == set(candidate_key):
            return False
    return True


def is_unique(key_comb, transposed_relation):
    tmp_set = set()

    for j in range(len(transposed_relation[0])):
        tmp_list = []
        for i in key_comb:
            tmp_list.append(transposed_relation[i][j])

        if tuple(tmp_list) in tmp_set:
            return False
        tmp_set.add(tuple(tmp_list))
    return True


def solution(relation):
    transposed_relation = list(zip(*relation))

    columns = [i for i in range(len(transposed_relation))]
    keys = []
    for i in range(1, len(columns) + 1):
        keys.extend(list(combinations(columns, i)))

    candidate_keys = []

    for key_comb in keys:
        if not is_minimum(key_comb, candidate_keys):
            continue

        if is_unique(key_comb, transposed_relation):
            candidate_keys.append(key_comb)

    return len(candidate_keys)

print(solution([["100","ryan","music","2"],["200","apeach"

사실 transpose를 하는 부분은 필요없는데 처음 문제를 잘못 생각해서 했고, transpose를 하는 공부가 되어서 그냥 놔뒀다.

다른 사람 풀이

from collections import deque
from itertools import combinations

def solution(relation):
    n_row = len(relation)
    n_col = len(relation[0])  

    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)

• candidates : combinations을 통해서 가능한 모든 경우의 수를 생성
• final : 가능한 모든 경우의 수에서 유일성을 만족하는 지 확인
  • 튜플 형태로 해당하는 값을 추출해서 길이가 맞는 지 확인합니다.
  • 예) (100, 200, ... , 600) 은 길이가 6으로 유일성 만족
• answer : 최소성을 만족하는 부분만 추출
  • intersection을 통해서 겹치는 변수가 원본 변수가 같은게 있는 지 확인