[프로그래머스 Lv.2] 후보키 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42890

프로그래머스

풀이

후보키의 조건은 유일성과 최소성을 만족하는 것이다. 그렇기에 주어진 데이터들을 적절한 형태로 가공하고, 유일성과 최소성이 만족되는지 확인하면 된다.

 

우선 유일성을 만족하는지 확인하는 작업은 set 자료구조를 사용하여 비교적 쉽게 생각할 수 있었다. 만약 유일성을 만족한다면 set에서 중복으로 걸러지는 요소가 없기 때문에, set의 크기와 전체 row의 크기가 동일할 것이다. 이 점을 사용해서 유일성을 만족하는 column의 조합을 결정할 수 있었다.

 

다만 어려웠던 점은 최소성을 확인하는 작업이었다. 처음에는 이미 후보키로 추가할지 체크하는 column의 조합을 이루는 요소 하나하나가 이미 후보키로 들어가 있는지를 체크하여 요소 모두가 들어가 있지 않는 경우엔 후보키로 추가하는 방식으로 시도했다. 예를 들어, (0번째 column)이 후보키로 들어가 있는 경우에 (0번째 column, 1번째 column)은 후보키로 추가되지 못하고, (2번째 column, 3번째 column)은 후보키로 추가하는 방식으로 시도한 것인데 이는 잘못된 방법이다.

왜냐하면 예를 들어 (0, 2)가 후보키인데 시도했던 방법을 그대로 적용하면 (0, 1)은 0이 이미 다른 후보키에 들어가 있기에 새로운 후보키로 추가되지 못하기 때문이다.

그래서 생각한 방법이 set의 issubset 메서드를 사용해서 이미 후보키로 저장된 조합들 중 하나라도 새로 추가될 column의 조합의 부분 집합인지 확인하는 방법이었다. 만약, 부분 집합이 되는 조합이 하나라도 있으면 이미 등록된 후보키에 포함되는 조합인 것이기에 최소성을 만족하지 못한 것이다.

from itertools import combinations

def solution(relation):
    answer = set()

    idxs = [n for n in range(len(relation[0]))]# 조합을 뽑기 위한 column의 번호들
    for n in range(1, len(relation[0]) + 1): # 튜플의 키가 될 갯수
        for comb in combinations(idxs, n): # 키의 조합 생성
            if not validate_minimality(comb, answer): # 최소성을 만족하지 않으면
                continue # 그 조합은 스킵

            checker = set()
            for row in relation:
                temp = []
                for idx in list(comb): # 키 조합을 사용해 튜플을 생성
                    temp.append(row[idx])
                checker.add(tuple(temp)) # 튜플을 저장하여
            if len(checker) == len(relation): # 전체 column의 수와 같으면 유일성이 보장됨
                answer.add(comb)

    return len(answer)

def validate_minimality(comb, answer): # 최소성 만족하는지 확인
    for existed_key in answer: # 이미 저장된 후보키 중에서 하나라도
        if set(existed_key).issubset(set(comb)): # 현재 체크하는 조합의 부분집합이라면
            return False # 최소성을 만족하지 않음
    return True