[programmers] 후보키(2019 KAKAO BLIND RECRUITMENT)

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

코딩테스트 연습 - 후보키

 

• 최근 문제를 풀면서 유형이 정해져 있지 않은 구현문제푸는 연습을 많이 해야겠다는 생각을 했습니다. 때문에 프로그래머스에서 2단계 문제들을 모두 풀어보고 있죠.
• 이 문제 또한 단순한 구현 문제인데, 생각하고 푸는데 꽤 오랜 시간이 걸렸습니다. 
• 문제를 요약정리해보면 '유일성, 최소성을 만족하는 경우의 수를 구해라' 인데요, 주어진 입력값의 범위가 크지 않아서 조합을 이용해서 나올 수 있는 경우의 수를 모두 구해주고, 나온 조합이 유일성과 최소성을 만족하면, answer에 담기게 했습니다.
• 자세한 내용은 주석을 참고해주시면 감사하겠습니다.

 

from itertools import combinations

def solution(relation):
    answer = 0
    length = len(relation)
    col_length = len(relation[0])
    combi = []
    for i in range(1, col_length+1):
    	# 나올 수 있는 조합의 경우의 수를 구해서 combi 리스트에 담아준다.
        combi.extend(combinations(range(col_length), i))
    # print(combi)
    unique = []
    for i in combi:
        # 릴레이션의 기준을 만들어서 그 기준에 맞게 값들을 출력해본다.
        # 가능한 모든 조합들
        tmp = [tuple([item[key] for key in i]) for item in relation]
        # print(i)
        # print(set(tmp))
        # print('-------------')
        # relation 길이와 set 적용한 길이가 같으면 -> 유일성 확인
        if len(set(tmp)) == length: # 유일성 체크
            unique.append(i)
    # 중복 없애기
    answer = set(unique)
    # 최소성은 꼭 필요한 것 끼리만 최소로 뭉쳐야한다.
    # 최소성 확인 -> 조합이 어떠한 조합의 부분집합이면 안된다.
    for i in range(len(unique)):
        for j in range(i+1,len(unique)):
            # j가 i의 부분집합인데 교집합이 i랑 같으면 j는 최소성을 만족하지 않는다.
            if len(unique[i]) == len(set(unique[i]) & set(unique[j])):
                # j 조합을 지운다.
                answer.discard(unique[j])
    # print(combi)
    # print(unique)
    # print(answer)
    return len(answer)