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

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

코딩테스트 연습 - 후보키

 

 

 

 문제 설명 

 

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

 

 알고리즘 

 

1. 먼저 각 열에대해 후보키가 될 수있는 모든 경우의 수를 조합으로 구한다.

2. 그리고 열에 해당해는 행들의 값을 Set() 형태로 넣는다.

3. set()형태로 넣으면 중복이 걸리지므로 원래 행의 길이와 set형태로 넣은 행의 길이를 비교해서 후보키가 가능한지 여    부를 판단한다.

4. 후보키의 후보를 추려낸후 최소성을 검증한다.

5. 최소성은 후보키의 후보중 길이가 짧은 것부터 확인하는데 길이가짧은 후보키의 후보가 다른 후보키의 후보에 들어

  있다면 길이가 더 짧은 후보키를 마지막 후보에 넣는다.

6. 유일성과 최소성으로 추려진 후보키를 return 

 

스스로 풀지못해서 다른 블로그를 참고함. ㅜ

 

 코드 

#후보키
from itertools import combinations
 
def solution(relation):
    answer = 0
    #모든 컬럼의 조합 리스트
    all = []
    
    # 유일성을 만족하는 조합 리스트
    uniqe = []
    
    if len(relation)>0:
        #컬럼의 갯수
        colSize = len(relation[0])
        # 로우의 개수
        rowSize = len(relation)
        
        #모든 컬럼의 조합 구하기(Set형태)
        for i in range(1,colSize+1):
            # extend
            all.extend([set(k) for k in combinations([j for j in range(colSize)],i)])
        # 조합들의 유일성 검증
        
        for comb in all:
            #set에 추가하여 사이즈 비교로 검증
            vaildSet = set()
            #조합에 해당되는 로우를 하나의 str로 합쳐서 set에 넣음
            for row in range(rowSize):
                temp=''
                for col in comb:
                    temp += relation[row][col]
                vaildSet.add(temp)
            # 유일성 확인하여 리스트에 추가
            if len(vaildSet) ==rowSize:
                uniqe.append(comb)
            
            #최소성 검증
            #삭제대상 Set(최소성 위배)
            delSet = set()
            #부분 집합 여부 확인
            for std in uniqe:
                for idx,comp in enumerate(uniqe):
                    #부분집합이면서 자기 자신이 아니라면 상위집합을 삭제 대상에 추가
                    if std.issubset(comp) and std !=comp:
                        #인덱스만넣음
                        delSet.add(uniqe.index(comp))
            # 유일성 - 최소성 위배 
            answer = len(uniqe)-len(delSet)                  
            
    return answer