2019 KAKAO BLIND RECRUITMENT- 후보키, 파이썬

1. 문제 

- 주어진 relation 배열에서 후보키를 구하는 문제

- 유일성과 최소성을 만족해야함

- 후보키의 개수를 리턴

 

2. 풀이

- 풀이 방법 자체는 어렵지 않게 떠올릴 수 있으나 좀 깔끔하게 짤 수 없을까 하다가 오래걸림

- 각 키들의 모든 조합을 구한 후 중복이 배열에 중복이 없는지 체크(유일성)

- 단 최소성을 만족시키기 위해 a 가 후보키인 경우 [a, c] 조합을 계산할 필요 없음

- return_cases 함수로 모든 조합을 구한 후(인덱스를 구했으나 그냥 문자열로 구하는게 편했을듯, 유효성 체크할때), 모든 케이스에 대해 check_dup로 중복이 있는지(유일성) 체크, 그 뒤에 val_check로 최소성 체크, 최소성 만족한다면 check에 후보키로 등록, 마지막에 후보키의 개수를 리턴해줌

- 키가 [a, b, c, d]라 했을 때 처음에 check = [0, 0, 0, 0]으로 하고 후보키에 등록하면 1로 바꿔주는 식으로 짰었는데 이럴 경우 [b, c] , [b, d]가 후보키로 체크가 안 됨(b, c 가 후보키로 등록되는 순간 b가 1로 체크되기 때문에) -> 문자열로 조합을 짜야 최소성 검사하기가 쉬웠을까? 좀 더 효율적으로 짜려고 인덱스로 조합을 만든건데 결국 더 비효율적으로 짜버림 

 

3. 코드

def solution(relation):
    col = len(relation[0])
    row = len(relation)
    cases = []
    for i in range(1, col+1) :
        return_cases(0, i, cases, [], col)
    check = []
    while cases :
        case = cases.pop(0)
        if check_dup(check, case) :
            continue
        if val_check(relation, case) :
            check.append(case)
    return len(check)

def return_cases(idx, n, cases, path, col) :
    if len(path) == n :
        cases.append(path)
    for i in range(idx, col) :
        return_cases(i+1, n, cases, path + [i], col)
        
def val_check(arr, case) :
    key = set()
    for i in range(len(arr)) :
        temp = tuple(arr[i][x] for x in case)
        if temp in key :
            return False
        else :
            key.add(temp)
    return True

def check_dup(check, arr) :
    for cand in check :
        for i in range(len(cand)) :
            if cand[i] not in arr :
                break
            if i == len(cand) - 1 :
                return True
    return False

4. 개선

- 조합이 파이썬 라이브러리에 있었음...

from itertools import combinations

arr = [1, 2, 3, 4, 5]
combi = list(combinations(arr, n)

-> 이런식으로 사용 가능함

 

- 비트마스크를 이용한 풀이도 가능함

해당 포스팅 참조 : itzjamie96.github.io/2020/10/15/python-bitwise-powersets/