[Python][2019 KAKAO] 프로그래머스 - 후보키(LEVEL2)

문제출처 - https://programmers.co.kr/learn/courses/30/lessons/42890

프로그래머스

from itertools import *

def checkMinimality(candidate, target):
    for i in range(len(candidate)):
        cnt = 0
        for j in range(len(candidate[i])):
            if candidate[i][j] in target:
                cnt += 1
        if cnt == len(candidate[i]):
            return False

    return True


def checkUniqueness(relation, combi):
    arr = []
    for i in range(len(relation)):
        temp = []
        for j in range(len(combi)):
            temp.append(relation[i][combi[j]])

        if temp in arr:
            return False

        arr.append(temp)

    return True


def solution(relation):
    answer = 0
    combiList = [i for i in range(len(relation[0]))]  # column 개수만큼 배열 할당
    combination = []  # 가능한 column의 모든 조합
    candidate = []  # 후보키 list

	# column으로 가능한 모든 조합 만들기
    for i in range(1, len(relation[0])+1):
        combination.append(list(combinations(combiList, i)))

	# 모든 조합의 유일성, 최소성 따져보기
    for i in range(len(combination)):
        for j in range(len(combination[i])):
			# 유일성, 최소성 둘다 만족하면 후보키에 추가
            if checkUniqueness(relation, combination[i][j]) and checkMinimality(candidate, combination[i][j]):
                answer += 1
                candidate.append(list(combination[i][j]))

    return answer

설명

 

1. column으로 만들수있는 가능한 모든 조합을 찾는다.

 

2. 유일성, 최소성을 만족하는지 체크한다.

 

 

checkMinimality

 

만약에 후보키 리스트(candidate)가 [[0], [1, 2]]이고 target이 [0, 3]인 경우

candidate[0][0]의 0이 target 안에 포함되어 있기 때문에 최소성을 만족하지 않아 false를 리턴한다.

 

candidate가 [[0], [1, 2]]이고 target이 [1, 2, 3]인 경우도 마찬가지로

candidate[1][0]의 1과 candidate[1][1]의 2가 모두 target에 포함되어 있기 때문에 최소성을 만족하지 않는다.

 

 

checkUniqueness

 

temp라는 배열에 각 튜플마다 조합(combi)에 해당하는 column의 값들을 넣어준다.

 

temp가 arr에 이미 존재한다면 유일성을 만족하지 않기 때문에 해당 조합(combi)는 후보키가 될 수 없다!!