후보키

코딩테스트 연습 - 후보키 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 후보키

풀이)

우선 몇개의 Attribute가 모여 후보키가 되는지 확인하기 위하여 각 Attribute에 1~n까지의 번호를 매겨

다음과 같이 조합을 구했다.

1개의 Attribute가 후보키인 경우

1,2,3,4,5,6

2개의 Attribute가 모여 후보키가 되는 경우 

(1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (2,5), 2,6), (3,4), (3,5), (3,6), (4,5), (4,6), (5,6)

6개의 Attribute가 모여 후보키가 되는 경우

(1,2,3,4,5,6)

 

위의 경우들 중 유일성을 만족하는 키를 찾기 위해 우선 각 Attibute집합을 list에 저장했고

각 경우에 따라 Attribute값들 합쳐 list를 재구성하고 중복을 확인했다.

만약 (1,2)와 같은 경우(1 == 학번, 2 == 이름을 뜻함)

100ryan

200apeach

300tube

위 리스트가 중복이 없는 경우 후보키임을 뜻한다.

 

최소성을 유지하기 위해서 위의 유일성을 만족하는 키를 찾는 과정에서 후보키가 되는 키들을 저장했고

이미 나온 키들을 포함하는 키들은 제외했다.

예를 들어 1개의 Attribute가 후보키인 경우를 탐색하다가 1번Attribute가 후보키라면

2개의 Attribute가 모여 후보키가 되는 경우를 탐색하는 도중에는 1번을 포함한 키들은 제외시킨다.

코드)

from itertools import product
from itertools import permutations 
from itertools import combinations
def unique(l):
    if len(l) == len(set(l)):
        return True
    else:
        return False
    
def solution(relation):
    answer = 0
    keys = []
    values = []
    items = []
#--------------------------------------------------
    for row in relation: #가로배열
        a = []
        for col in row:
            a.append(col)
        keys.append(a)


    for k in range(len(keys[0])): # 세로배열(Attribute 집함)
        u = []
        for v in range(len(keys)):
            u.append(keys[v][k])
        values.append(u)

    isTrue = 0
    for i in range(0,len(relation[0])):
        items.append(i)
    unique_keys = []
    for i in range(1,len(items)+1):
        A = list(combinations(items,i)) # 후보 키의 개수
        for k in A: # 후보 키의 개수에 따른 조합
            k = list(k)
            min = 0
            for unique_key in unique_keys:
                min = 0
                for ukey in unique_key:
                    if ukey in k:
                        min = 1
                    else:
                        min = 0
                        break
                if min == 1:
                    break
            if min == 1:
                continue
            subkey = []
            for l in range(len(values[0])):
                newvalues =''
                for n in k:
                    newvalues += keys[l][n]
                subkey.append(newvalues)    
            if unique(subkey) == True:
                unique_keys.append(k)
                answer = len(k)
    answer = len(unique_keys)
    return answer