(Python) [2019카카오공채] 후보키

출처 : https://programmers.co.kr/learn/courses/30/lessons/42890#

코딩테스트 연습 - 후보키 | 프로그래머스

# code

from itertools import chain, combinations
 
 
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))
 
 
def solution(relation):
    n, m = len(relation), len(relation[0])
    ## key_candi를 만드는 작업
    key_candi = []
    for key in powerset(range(m)):
        aset = set()
        for i in range(n):
            aset.add(tuple(relation[i][j] for j in key))
        if len(aset) == n: key_candi.append(key)
    
    ## key_candi2를 만드는 작업
    key_candi2 = []
    for i in range(len(key_candi)-1, -1, -1):
        for j in range(i-1, -1, -1):
            if set(key_candi[i]) & set(key_candi[j]) == set(key_candi[j]):
                key_candi2.append(key_candi[i])
                break
    return len(key_cd) - len(key_cd2)

---

# 자세한 설명

(Python) [2019카카오공채] 후보키¶

출처 : https://programmers.co.kr/learn/courses/30/lessons/42890#

---

In [67]:

from itertools import chain, combinations

아래 함수 powerset의 목적은 모든 부분집합을 구하고자 하는데 있다.

파이썬 documentation에서 가져왔다.
파이썬의 itertools 라이브러리를 이용해서 만들 수 있다.
itertools의 chain과 combination을 응용한다.
출처 : https://docs.python.org/3/library/itertools.html

공집합을 제외한 부분집합들에 관심이 있기 때문에, range(len(s)+1)을 range(1, len(s)+1)로 수정한다.

In [68]:

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(1, len(s)+1))

집합(set)으로 묶어줄 경우, 중복된 경우의 수를 제거해주기 때문에
선택된 열들에 의해 만들어진 집합의 길이가 원래 처음 데이터(=relation)의 길이(=세로길이, 데이터갯수)와 동일하다면
잠정적 후보키로 판단을 해서 key_candi에 추가한다.

key_candi를 만드는 작업이 끝나고 나면, key_candi2를 만들기 시작한다.
key_candi중에서 후보키가 될 수 없는 요소들을 선별하여 key_candi2에 추가한다.
이 작업이 모두 끝나고나면, key_candi중에서 key_candi2를 제외한 나머지들이 후보키가 되므로
후보키 갯수에 관심이 있다면 길이 차이를 계산해주면 되고
후보키 자체에 관심이 있다면 차집합 함수를 사용하면 된다.

In [69]:

def solution(relation):
    n, m = len(relation), len(relation[0])
    ## key_candi를 만드는 작업
    key_candi = []
    for key in powerset(range(m)):
        aset = set()
        for i in range(n):
            aset.add(tuple(relation[i][j] for j in key))
        if len(aset) == n: key_candi.append(key)
    
    ## key_candi2를 만드는 작업
    key_candi2 = []
    for i in range(len(key_candi)-1, -1, -1):
        for j in range(i-1, -1, -1):
            if set(key_candi[i]) & set(key_candi[j]) == set(key_candi[j]):
                key_candi2.append(key_candi[i])
                break
    return len(key_cd) - len(key_cd2)

In [70]:

relation = [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]

In [71]:

relation

Out[71]:

[['100', 'ryan', 'music', '2'],
 ['200', 'apeach', 'math', '2'],
 ['300', 'tube', 'computer', '3'],
 ['400', 'con', 'computer', '4'],
 ['500', 'muzi', 'music', '3'],
 ['600', 'apeach', 'music', '2']]

In [72]:

solution(relation)

Out[72]:

2

---

이해를 돕기 위해 key_candi와 key_candi2를 살펴보자.¶

• relation은 위에서 이미 값을 할당해주었다.

In [74]:

n, m = len(relation), len(relation[0])
print(n, m)   # 세로(n), 가로(m)

6 4

In [75]:

## key_candi를 만드는 작업
key_candi = []
for key in powerset(range(m)):
    aset = set()
    for i in range(n):
        aset.add(tuple(relation[i][j] for j in key))
    if len(aset) == n: key_candi.append(key)

In [76]:

## 잠정적 후보키 가능성이 있는 열들의 모임
key_candi

Out[76]:

[(0,),
 (0, 1),
 (0, 2),
 (0, 3),
 (1, 2),
 (0, 1, 2),
 (0, 1, 3),
 (0, 2, 3),
 (1, 2, 3),
 (0, 1, 2, 3)]

In [77]:

## key_candi2를 만드는 작업
key_candi2 = []
for i in range(len(key_candi)-1, -1, -1):
    for j in range(i-1, -1, -1):
        if set(key_candi[i]) & set(key_candi[j]) == set(key_candi[j]):
            key_candi2.append(key_candi[i])
            break

In [78]:

## 잠정적 후보키 목록(=key_candi)에서 더이상 후보키가 될 수 없다고 판단된 요소들
key_candi2

Out[78]:

[(0, 1, 2, 3),
 (1, 2, 3),
 (0, 2, 3),
 (0, 1, 3),
 (0, 1, 2),
 (0, 3),
 (0, 2),
 (0, 1)]

따라서 후보키 목록을 보고 싶다면, 차집합을 이용하면 쉽다.

In [79]:

set(key_candi) - set(key_candi2)

Out[79]:

{(0,), (1, 2)}

결과적으로, 0번째 열만 이용하거나, 1번, 2번 열을 함께 사용하면 후보키로 사용할 수 있다.

In [81]:

## 단순히 갯수만 관심이 있는 것이라면, 굳이 리스트를 집합으로 변환시켜 줄 필요도 없다.
len(key_candi) - len(key_candi2)

Out[81]:

2