[프로그래머스] 후보키 파이썬

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

코딩테스트 연습 - 후보키

 

조합으로 풀이했다.

 

후보키의 길이는 1,2,3,4,..최대 8까지다.

그러므로 속성중에서 1개,2개,3개 뽑는 경우의 모든 조합을 다 구해도 충분하다.

 

우선 후보키가 될 컬럼들을 뽑아 조합을 순서 조합을 만들자.

다음 뽑은 조합으로 나는 최소성을 만족하는지 확인했다.

 

나는 이전 단계에서 뽑은 후보키의 컬럼 조합을 used에 저장했다.

그래서 used에 뽑은 조합이 현재 조합에 포함되는지 확인한다.

이는 그냥 for문으로 구성했다.

 

다음 유일성을 만족시키는지 확인한다.

이는 위에서 만든 조합으로 key를 만들고 중복되는지 확인만 하면 된다.

이때 주의할 점이 key를 만들때 각 속성별로 구분지어줄 문자를 넣어줘야한다.

예를 들어

데이터가 [[1,11],과 [11,1]]이 있고 키 조합이 (0,1)이라면

만들어진 키는 두개 모두 111, 111이다. 실제론 1 11, 11 1로 다른 키여서 유일성을 만족시키지만 속성별로 구분이 안되서 같은 값을 가지게 된다. 따라서 이를 위해 속성별로 구분할 수 있는 문자를 넣어준다.

 

다음 유일성까지 만족했다면 해당 조합은 후보키를 만족하므로 used 배열에 넣고 답을 갱신한다.

 

from itertools import combinations
def solution(relation):
    global n,used
    n = len(relation[0])
    used = []
    answer = 0
    
    for count in range(1,n+1):
        for order in combinations(range(n),count):
            if is_used(order):
                continue
            if is_possible(order, relation):
                answer += 1
                used.append(order)
    return answer

def is_possible(order,relation):
    keys = set()
    
    for row in relation:
        key = ''
        for idx in order:
            key += '-'+row[idx]
        if key in keys:
            return False
        keys.add(key)
        
    return True
        
def is_used(order):
    for arr in used:
        count = 0
        for idx in arr:
            if idx in order:
                count += 1
        if count == len(arr):
            return True
    return False