[프로그래머스] 후보키 [python]

문제

조합과 구현을 섞어 놓은 문제였다. 구현을 잘 한다면 풀 수 있는 문제이다.

 

코드

def solution(relation):
    global answer
    answer = 0
    candidates = []
    for i in range(1,len(relation[0]) + 1): ## 조합
        combination([], i, 0, relation, candidates)
    return len(candidates)

def combination(comb, maxLen, nextN, relation, candidates):
    global answer
    if isInCandidates(comb, candidates): 
        return
    if maxLen == len(comb):
        if canUseCandidateKey(comb, relation) == False:
            return
        answer += 1
        candidates.append(tuple(comb))
        return
    for i in range(nextN, len(relation[0])):
        comb.append(i)
        combination(comb, maxLen, i + 1, relation, candidates)
        comb.pop(-1)

def canUseCandidateKey(comb, relation):
    allValues = []
    for r in relation:
        tmp = []
        for i in comb:
            tmp.append(r[i])
        if tmp in allValues:
            return False
        allValues.append(tmp)
    return True
def isInCandidates(comb, candidates):
    for i in candidates:
        cnt = 0
        for k in list(i):
            if k in list(comb):
                cnt += 1
        if cnt == len(i): 
            return True
    return False

"""
완전 탐색
comb에 있는 값들은 어떤 컬럼을 쓰는 지,
"""