프로그래머스 후보키

문제 보러 가기

백트래킹과 집합 연산으로 풀이

개념 확인

• 슈퍼키: 유일성만 보장하는 키
• 후보키: 최소성도 보장하는 키

풀이

1. 모든 키 집합에 대해 슈퍼키인지 확인한다. 백트래킹으로 구현한다.
2. 슈퍼키라면 후보키 리스트의 모든 후보키와 집합 연산한다.

예를 들어,

현재까지 구한 후보키: [ {1, 2}, {1, 2, 4}]
슈퍼키(후보키 후보): {1, 2, 3}

일때, 슈퍼키를 모든 후보키와 집합 연산을 하면

연산 결과:
1. {1, 2} & {1, 2, 3} = {1, 2} (후보키 자체)
2. {1, 2} & {1, 2, 4} = {1, 2} (후보키가 아님)

이게 무슨 의미냐?

연산 결과==해당 후보키 : 최소성 만족하지 않는다는 의미, 후보키가 될 수 없다.
연산 결과 != 해당 후보키 : 후보키가 될 수 있다.

3. 집합 연산은 파이썬 Set 연산이나 비트 연산으로 처리한다.

코드

fields = [] # 필드 조합
superkeys = [] # 슈퍼키
candidates = [] # 후보키

def solution(relation):
    global fields, superkeys, candidates
    # 후보키로 선정됐는지 판단
    N = len(relation)
    K = len(relation[0])
    answer = 0

    # 비트 연산
    def is_candidate(fields: str):
        bit = ''.join(['1' if field in fields else '0' for field in range(K)])
        decimal = int(bit, 2)
        for candidate in candidates:
            if bin(decimal & candidate) == bin(candidate):
                return False
        return True

    def is_superkey(fields):
        strings = ['' for _ in range(N)]
        for field in fields:
            for index in range(N):
                strings[index] += relation[index][field]
        return len(strings) == len(set(strings))

    # 백트래킹으로 후보키가 되는지 판단
    def search_superkeys(count, index):
        if len(fields) == count and is_superkey(fields) and is_candidate(fields):
            field_bit = int(''.join(['1' if field in fields else '0' for field in range(K)]), 2)
            candidates.append(field_bit)

        for field in range(index, K):
            if len(fields) < count:
                fields.append(field)
                search_superkeys(count, field + 1)
                fields.pop()

    # count만큼의 필드를 조합해 후보키 판단
    for count in range(1, K + 1):
        search_superkeys(count, 0)
    return len(candidates)

어렵다