LV2 [KAKAO] 후보키

---

문제

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

프로그래머스

 

풀이

얏호

 

처음에 후보키 개념이 애매모호해서, 그것부터 정리하고 문제풀이를 시작했다.

 

문제의 핵심은 유일성보다는 최소성을 어떻게 판별할것인가, 였던거 같다.

 

최소성을 판별하기 위해서는 부분집합을 활용하면 된다.

 

만약 속성이 '학번' , '이름', '학년' 이라고 가정해보자.

이 때 '학번' 하나만으로도 후보키가 될 경우, '학번' 이 특정 집합의 부분집합이 되는 순간 최소성을 위반한다.

'학번' 하나만으로도 구분이 가능하므로, 다른 속성들이 끼어들 필요가 없기때문이다.

2개 이상일때도 마찬가지이다. ('이름', '학년') 이라는 키가 후보키가 된다면 이를 부분집합으로 가지는 값들은 후보키가 될 수 없다.

유일성 같은 경우에는 set과 같은 중복을 허용하지 않는 자료구조를 활용하여 개수가 맞는지만 판단해주면 된다.

 

따라서 속성을 하나씩, 두개씩, n개씩 고르는 모든 경우의 수를 만들어보고, 이미 후보키로 지정된 값들을 부분집합으로 가지지 않으면서, 유일성을 만족하는 값들을 후보키로 지정해주면 된다.

 

비교할때는 set으로 부분집합을 판별할 수 있기 때문에 set으로 변환해주었다.

또한 set에는 immutable 객체가 들어가야해서 list인 arr변수를 tuple로 바꾸어 준 후에 set에 넣어주었다.

코드

combo = []

def dfs(idx, limit, temp):
    if idx>=limit :
        combo.append(temp)
        return

    dfs(idx+1, limit, temp)
    temp2 = copy.deepcopy(temp)
    temp2.append(idx)
    dfs(idx+1, limit, temp2)
    return


def solution(relation):

    attribute = len(relation[0])
    count = len(relation)

	# 모든 경우의 수 만들어주고, 리스트 길이순으로 정렬해준다.
    dfs(0, attribute, [])
    combo.sort(key=len)

    # 후보키 저장 집합
    possible = set()

    # 모든 경우의 수 탐색 [0], [0, 1] ...

    for com in combo:
        s = set()
        flag = False
        # 부분집합으로 존재한다면 나간다.
        for val in possible:
            if set(val) <= set(com):
                flag = True
                break
        if flag : continue
        for i in range(count):
            arr = []
            for c in com:
                arr.append(relation[i][c])
            s.add(tuple(arr))
        # 중복이 없다면
        if len(s) == count:
            possible.add(tuple(com))

    return len(possible)

 

후기

 

tuple이나, set이나 평소에 사용해본적이 많지 않아서 코드가 너무 지저분하다..

또한 후보키의 명확한 개념을 알지 못하여서 부분집합 정의하기가 어려웠다.

꾸역꾸역 코드짜긴했는데 맞아서 다행이다 ㅎ 

 

* dfs로 모든 경우의수를 바보 같이 구했는데 combination 을 for문 돌리면 모든 경우의 수를 구할 수 있었다. for문 생각을 못했네..