문제

https://school.programmers.co.kr/learn/courses/30/lessons/42890#

풀이

아이디어

• 조합을 이용한다. (문제 읽으면서 데이터베이스 후보 키 나오자마자 조합으로 복잡하게 구현하는 거겠구나 생각함)
• 유일성과 최소성을 판별해주는 함수를 짠다
  • 이때 난 set을 이용해주었다. (중복된 데이터가 있어서 유일성을 만족하지 못한다면 원래 데이터베이스의 Row의 수와 같지 않을 것이므로)
• 주의사항) answer이 0일 수는 없으므로 0일 때는 1을 리턴해주어야 한다. (무조건 모든 컬럼을 고르는 한이 있더라도 정답인 경우는 1개 이상 존재하므로)

코드

from itertools import combinations

def solution(relation):
    ROW = len(relation)
    COL = len(relation[0])
    columns = [i for i in range(COL)]
    answer = 0
    
    #input: 선별된 컬럼들의 리스트
    def check_min(cols):
        #하나를 제외했을 때 유일성이 깨지는 지 보자.
        if len(cols) == 1:
            return True
        
        for i in range(len(cols)):
            unique_set = set()
            test_cols = cols[:i] + cols[i+1:]
            s = ''
            for r in range(ROW):
                for c in test_cols:
                    s += relation[r][c]
                unique_set.add(s)
                s = ''
            if ROW == len(unique_set):
                return False
        
        return True
        
    for i in range(COL):
        combs = combinations(columns, i)
        for comb in combs:
            cols = list(comb)
            unique_set = set()
            for r in range(ROW):
                s = ''
                for col in cols:
                    s += relation[r][col]
                unique_set.add(s)
                s = ''
            if ROW == len(unique_set):
                if check_min(cols):
                    # print('cols: ', cols)
                    answer += 1
    
    return answer if answer > 0 else 1