[프로그래머스] Lv2. 후보키 (2019 카카오 공채)

🔗

풀이

유일성 : 튜플을 유일하게 식별할 수 있어야 한다
최소성 : 꼭 필요한 속성으로만 구성되어야 한다.

유일성을 만족하는 조합에 대해서는 그 조합 자체를 제외한, 그 조합을 포함하는 다른 조합들은 제거해야 한다

만약 a라는 튜플이 유일성을 만족한다면 a자체를 제외한 a를 포함하는 모든 조합에 대해서는 유일성을 만족하더라도 최소성을 만족할 수 없다. 이미 a만으로도 식별이 가능하기 때문이다. 각 조합들에 대해서 차례대로 유일성을 확인하면서 이미 앞서 유일성이 확인된 조합을 포함하고 있는 조합이라면 건너뛰어야 한다.

현재 풀이에서는 유일성을 만족하는 가능한 모든 조합을 구한 후, 각 조합을 모두 돌면서 최소성을 만족하는지 확인하는 방식으로 구현했다.

def solution(relation):
    rows = list(zip(*relation))
    cols = list(range(len(rows)))

    def check_candidate(comb):
        lst = list(zip(*[rows[x] for x in comb]))

        return len(lst) == len(set(lst))

    def check_minimal(i, x):
        result = {i}
        for j, y in enumerate(combs):
            for c in x:
                if c not in y:
                    result.add(j)
                    break  
        return result
	
    # 모든 조합 구하기
    def dfs(k, comb):
        nonlocal combs
        # 유일성을 만족하는 조합들만 combs에 추가
        if comb and check_candidate(comb):
            combs.append(comb)
            return 

        if k == len(cols):
            return 

        for i in range(k, len(cols)):
            dfs(i+1, comb+[i])

    combs = []
    dfs(0, [])

    combs.sort(key=lambda x: len(x))
	
    # 각 combs의 원소들에 대해서 다른 원소중에 현재 원소를 포함하고 있는 원소가 있다면 제외
    # 포함하지 않는 원소들에 대해서만 값을 반환하고 반환되는 값들의 교집합만 구함
    ans_set = set([i for i in range(len(combs))])
    for i, x in enumerate(combs):
        ans_set &= check_minimal(i, x)

    return len(ans_set)

🤩 부분집합을 활용한 풀이(참고)

부분집합과 비트 연산을 활용한 풀이. 각 컬럼에 대해서 후보키 조합에 포함이 되거나 되지 않거나 두 가지 경우 중 하나기 때문에 0, 1 2개의 값을 갖는 비트로 나타낼 수 있다. 또 부분집합으로 구하게 되면 각 조합을 001, 010, 011과 같이 단계별로 포함되는 개수가 작은 것부터 구할 수 있기 때문에 시간상 훨씬 유리하다.

우선 가능한 조합을 구한 후, 그 조합이 최소성을 만족하는지 확인하고, 그 다음 조합이 유일성을 만족하는지 확인한다. 비트 연산을 통해 비교하기 때문에 인덱스 값만을 조합 리스트인 combination에 저장하면 된다.

def solution(relation):
    rows = list(zip(*relation))
    combination = []
    
    # 유일성 확인(후보키인가)
    def check_candidate_key(comb):
        rows_comb = list(zip(*[rows[x] for x in comb]))
        return len(rows_comb) == len(set(rows_comb))
    
    # 최소성 확인
    def check_minimal(i):
        for j in combination:
            if i & j == j:
                return False
        return True
    
    for i in range(1, 1<<len(rows)):
        comb = []
        for j in range(len(rows)):
            if i & (1 << j):
                comb.append(j)
        
        # 최소성을 확인하고 유일성 확인하기
        if check_minimal(i) and check_candidate_key(comb):
            combination.append(i)
            
    return len(combination)