[Python] 카카오 2019 채용 - 후보키

https://programmers.co.kr/learn/courses/30/lessons/42890?language=python3

코딩테스트 연습 - 후보키

풀이

노가다로 풀었다...

from itertools import combinations

def make_key(relation, colList):
    alist = []
    for i in range(len(relation)) : 
        key = ""
        for col in colList:
            key += relation[i][int(col)]
        alist.append(key)
    return alist

def uniqueness(alist):
    if len(alist) == len(set(alist)) : return True
    return False

def minimality(candi_k, alist):
    flag = True
    for i in range(len(candi_k)):
        for x in candi_k[i]:
            if x in alist : flag = True
            elif x not in alist: 
                flag = False
                break
        if flag: return False
    return True


def solution(relation):
    answer = 0
    
    candi_k = []
    colList = []
    #col 1개로 이루어진 key
    for j in range(len(relation[0])):
        if uniqueness(make_key(relation, [j])) :
            candi_k.append([j])
        else : colList.append(str(j))
    
    #k개의 col로 구성된 복합키
    for k in range(2, len(colList)+1):
        combination = list(combinations(colList, k))
        for combi in combination:
            #유일성, 최소성 검사
            if uniqueness(make_key(relation, combi)) and minimality(candi_k, list(combi)) :
                candi_k.append(list(combi))
        
    answer = len(candi_k)
    return answer

 

다른 사람의 풀이

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)

 

def solution(relation):
    def is_powerset(parent, child):
        return parent | child == parent


    n_attr = len(relation[0])
    candidate_key = []

    for key in range(1, 1 << n_attr):
        #minimality
        flag = False
        for e in candidate_key:
            if is_powerset(key, e):
                flag = True
                break
        if flag:
            continue

        # uniqueness
        sliced_relation = []
        for row in relation:
            sliced_row = []
            for j in range(0, n_attr):
                if (key >> j) & 1 == 1:
                    sliced_row.append(row[j])
            sliced_relation.append(tuple(sliced_row))

        if len(sliced_relation) != len(set(sliced_relation)):
            continue

        candidate_key.append(key)

    answer = len(candidate_key)
    return answer

조합 대신 비트를 사용하면 간결하다

 

1 << n_attr(== 4) 

: [1,2,3,4,5,6,7,8,9,1]

 

테스트케이스에서 column이 4개이므로 0001 ~ 1111로  복합키를 표현할 수 있다

예) 1째 컬럼만으로 구성 => 0001

1,3째 컬럼만으로 구성 => 0101 ( = 5)

 

그래서 최소성을 확인할 때

0101 | 0001 == 0101 이므로 최소성을 만족하지 않는 복합키이므로 유일성검사도 할 필요가 없다

만약 포함하지 않는 복합키들을 검사한다면

0101 | 0010 = 0111 ( 1,3째 컬럼으로 구성된 복합키는 2째 컬럼으로 구성된 키를 포함하지 않으므로 최소성을 만족한다)

 

 

참고

1. list 모든 요소의 개수 세기.  dictionary 타입으로 return.

from collections import Counter

def unique(alist):
	result = Counter(myList)
	print result

	for key in result:
    	print key, result[key]

 

유일성을 만족하는지 확인하는 함수를 짰었는데

그냥 더 간단하게 len(set(alist)) == len(alist) 로 풀었다 

# 개수가 1개가 아닌게 있는지 확인
from collections import Counter

def unique(alist):
     result = Counter(alist).values()
     for val in result:
         if val != 1 : return False
     return True

 

 

2. list의 요소 삭제

alist.remove(ELEMENT)
del alist[INDEX]

 

 

3. 순열과 조합, 그리고 여러개의 리스트에서 조합

alist = [1,2,3]
k = 2

#순열 
from itertools import permutations

print(list(permutations(alist, k)))
#[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]




#조합
from itertools import combinations

print(list(combinations(alist, k)))
# [(1, 2), (1, 3), (2, 3)]




from itertools import product

alist = [[1,2,3], ['a','b']]
print(list(product(*alist)))
#[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')]