[2019 KAKAO BLIND RECRUITMENT] 후보키

문제

• 학생들의 인적사항이 주어졌을 때 후보 키의 최대 개수 구하기
• 1 <= 인적사항 개수 <= 8
• 1 <= relation 개수 <= 20

 

풀이 (1h 30mins...)

• 최소성 -> 이미 후보키가 될 수 있는 조합에는 추가 컬럼을 더하면 안된다.
• 유일성 -> 해당 후보키를 조합한 데이터는 단 하나만 존재해야 한다.

 

• ✅ 최소성 판단에서 막힘
• 처음에는 후보키를 생성하는 방식으로 접근했는데 계속 중복되는 경우가 발생함
  • [0, 1, 2, 3] 키 중 후보키를 찾기 -> [ 1, 2, 3] 중에서 길이가 2인 후보키 찾기 -> [(1, 3), (2, 3)] 중 길이가 3인 후보키 찾기
•  결국 중복을 완벽하게 제어하는 방법을 못찾아서 전체 컬럼 조합에서 최소성을 만족하지 못하는 키를 제거함

 

from collections import deque
from itertools import combinations

# 유일성 확인 (해당 키 조합의 데이터가 단 하나 존재하는지 확인)
def unique(cand, relation) :
    tmp = dict()
    for r in relation :
        key = " ".join([r[i] for i in cand])
        if key in tmp :
            return False
        else :
            tmp[key] = 1
    return True

# 최소성 확인 (해당 키 조합의 subset이 이미 후보키에 있는지 확인)
def minimality(cand, keys) :
    for k in keys :
        if set(k).issubset(set(cand)) :
            return False
    return True

def solution(relation):
    col = len(relation[0])  # 열 개수
    
    # 전체 컬럼 조합
    cands = []
    for i in range(1, col) :
        cands.extend(combinations(range(col), i))
    
    keys = set()            # 후보키 리스트
    for cand in cands :
        # 최소성과 유일성을 만족한다면 후보키에 추가한다.
        if minimality(cand, keys) and unique(cand, relation) :
            keys.add(tuple(cand))
    answer = len(keys)
    return answer if answer else 1

 

 

풀이2

• 전체 키조합을 구한 뒤, 최소성과 유일성을 만족하는지 확인한다.

 

2023.09.04 2차 풀이

from itertools import combinations

# 최소성 확인하기
def check_minimality(num, cols, candidates) :
    for cnt in range(1, num) :
        for c in combinations(cols, cnt) :
            if c in candidates :
                return False
    return True
    
def solution(relation):
    data_n = len(relation)      # 데이터 개수
    col_n = len(relation[0])    # 컬럼 개수
    candidates = set()          # 후보키 리스트
    
    # 전체 키조합 구하기
    for cnt in range(1, col_n+1) :
        for candidate in combinations([i for i in range(col_n)], cnt) :

            # 최소성 확인
            if not check_minimality(cnt, candidate, candidates) :
                continue
      
            # 유일성 확인
            data = set()
            for i in range(data_n) :
                data.add(tuple([relation[i][col] for col in candidate]))

            if len(data) == data_n :
                candidates.add(candidate)

    return len(candidates)