[프로그래머스/python] 후보키

알고리즘 후보키

후보키

2019 KAKAO BLIND RECRUITMENT

​

문제

프로그래머스

​

풀이

조합과 집합을 사용하여 풀이를 진행했습니다.

​

이 문제를 들었던 생각은 유일성과 최소성을 잘 구현하면 되겠다고 생각했습니다.

combinations 사용해서 후보키의 길이를 1부터 n열까지 올리면서 조합을 구했습니다.

조합의 값을 통해서 각 열에 있는 값들을 종합하여 겹치는 값이 있는지 집합을 썼습니다.

그럼 이제 유일성은 해결했습니다.

​

최소성의 경우 유일성에서 통과한 후보키 값을 n길이 조합이 유일성 검사하기 전에 체크합니다.

부분 집합으로 존재하는지 확인하기 위해 차집합을 사용했습니다. 이렇게 최소성도 해결했습니다.

​

설명 순서를 반대로 했지만 충분히 이해하시라고 생각합니다.

​

풀이코드

import itertools

def solution(relation):
    answer_list =[] # 정답들 : 후보키들
    order_li= [] # 후보키 순서
    tuple_length = len(relation[0]) # 튜플 길이
    numbers = [i for i in range(len(relation[0]))] # 순서를 정하기위한
    n= 1 #후보키 길이
    while(n<=tuple_length): # 후보키 길이가 튜플길이를 넘어가기 전까지 순환
        order_li = list(itertools.combinations(numbers, n)) # n길이의 조합으로 후보키에 해당하는 순서 만들기
        for order in order_li:
            # 최소성 확인
            check = False
            for answer in answer_list:# order에 이미 정답이 포함되는지 확인
                if set(answer) - set(order):
                    continue
                else:
                    check = True
                    break
            if check: # 이미 최소성 만족하는 원소있으므로 다음 order로 진행
                continue 

            #유일성 확인
            tuple_li = []
            for _tuple in relation:
                key = ''# 후보키
                for o in order:
                    key+=_tuple[o]
                tuple_li.append(key)
            if len(tuple_li) == len(set(tuple_li)): # 후보키 중복 검사
                answer_list.append(order)
        n+=1
    return len(answer_list)
    
    

​

가장 인기 많은 코드

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)