프로그래머스 : 후보키 (python)

프로그래머스 Level 2 : 후보키

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42890

전체 코드

from itertools import combinations

def combine_keys(keys, index):
    combine_keys_list = []
    
    for i in range(len(keys[0])):
        combine_key = ""
        for j in range(len(index)):
            combine_key += keys[index[j]][i]
        combine_keys_list.append(combine_key)
    return combine_keys_list
        
    
def solution(relation):
    
    res = 0
    keys = []
    for i in range(len(relation[0])):
        tmp = []
        for j in range(len(relation)):
            tmp.append(relation[j][i])
        keys.append(tmp)
    
    not_unique_keys = []
    for i in range(len(keys)):
        if len(set(keys[i])) == len(keys[i]):
            res += 1
        else:
            not_unique_keys.append(i)
    
    candidate_keys = [] # 1 2 3
    for i in range(2, len(not_unique_keys)+1):
        candidate_keys.extend(combinations(not_unique_keys, i))
    
    candidate_keys.sort(key=len)
    exclude_keys = []
    for c in candidate_keys:
        flag = False
        for ex in exclude_keys:
            if ex & set(c) == ex:
                flag = True
                break

        if not flag and len(set(combine_keys(keys, c))) == len(combine_keys(keys, c)):
            res += 1
            exclude_keys.append(set(c))
    
    return res

코드 작성시 고민했던 점과 배운 점

1. 칼럼별로 배열 다시 만들기!

• 유일성을 판별하기 위해서는 칼럼별로 중복된 값이 있는지 확인해야되기 때문에 칼럼별로 배열을 다시 만들어 주었다.
• 제가 편하게 구현하기 위해 구현한 로직이다.
• ex) [['100', '200', '300', '400', '500', '600'], ['ryan', 'apeach', 'tube', 'con', 'muzi', 'apeach'], ['music', 'math', 'computer', 'computer', 'music', 'music'], ['2', '2', '3', '4', '3', '2']]

 keys = []
 for i in range(len(relation[0])):
 	tmp = []
    for j in range(len(relation)):
   		tmp.append(relation[j][i])
    keys.append(tmp)

2. 먼저 단독으로 유일성을 만족하는 키 걸러내기

• 후보키 조합을 짤 때, 단독으로 유일성을 만족하는 키가 포함된다면 최소성을 만족시키지 못하기 때문에 후보키 조합을 구성할 때 제외시킨다.
• 유일성을 만족하는지에 대한 검증은 set을 적용 전과 후의 길이를 비교하여 중복이 있는지 없는지 검사하여, 길이가 같다면 해당 키로 모든 튜플을 식별할 수 있다는 뜻이기 때문에 단독적으로 유일성이 만족하는 키라고 판단하였다.
• 또한 단독으로 유일성을 만족하는 키는 후보키이기 때문에 후보키 개수(res)에 1을 더해준다.
• 단독으로 유일성을 만족하지 않는 키의 인덱스를 not_unique_keys에 저장한다.

not_unique_keys = []
for i in range(len(keys)):
    if len(set(keys[i])) == len(keys[i]):
        res += 1
    else:
        not_unique_keys.append(i)

3. 단독으로 유일성이 만족하지 않는 키들에 대해서 모든 조합을 구하기

• python 라이브러리인 combinations를 이용하여 단독으로 유일성을 만족하지 않는 키들에 대해서 모든 후보키의 인덱스 조합을 구한다.
• 이후 조합내의 키들의 길이에 따라 정렬을 한다. 왜냐하면 이후 최소성을 검증할때, 길이가 짧은 조합이 최소성이 만족한다면 그 이후에 있을 조합에 해당 조합이 포함되어있는 경우 이 조합은 최소성을 만족하지 않다고 거르기 위해서다.

candidate_keys = []
for i in range(2, len(not_unique_keys)+1):
    candidate_keys.extend(combinations(not_unique_keys, i))
    
candidate_keys.sort(key=len)

4. 최소성 검증

• 방금전에 단독으로 유일성이 만족하지 않는 키들에 대해서 모든 조합을 구했다. 이후 길이순으로 정렬도 했다.
• 해당 조합이 유일성이 만족하는지 검증하는 과정에서 해당 조합내의 칼럼을 String으로 합쳐주었다.
• ex) ['ryanmusic', 'apeachmath', 'tubecomputer', 'concomputer', 'muzimusic', 'apeachmusic']

def combine_keys(keys, index):
    combine_keys_list = []
    
    for i in range(len(keys[0])):
        combine_key = ""
        for j in range(len(index)):
            combine_key += keys[index[j]][i]
        combine_keys_list.append(combine_key)
    return combine_keys_list

• 그럼 2번 과정과 같이 set을 적용하고 길이 비교를 통해 해당 조합이 유일성이 만족하는지 안하는지 검증할 수 있다.

exclude_keys = []
for c in candidate_keys:
        flag = False
        for ex in exclude_keys:
            if ex & set(c) == ex:
                flag = True
                break

        if not flag and len(set(combine_keys(keys, c))) == len(combine_keys(keys, c)):
            res += 1
            exclude_keys.append(set(c))

• 하지만 해당 조합이 유일성을 만족하더라도 최소성도 만족하는지 확인하고 결과값에 1 증가해주어야하는데, 길이가 짧은 순부터 유일성을 판단하기 때문에 만약 유일성을 만족한다면 exculde_keys에 해당 조합의 인덱스를 넣어준다.
• 이후 다른 조합에 exclude_keys에 저장되어 있는 인덱스가 포함된 조합은 최소성이 만족하지 않기 때문에, 유일성까지 체크하지 않고 다음 조합을 검증하면 된다.!

결과