[프로그래머스 LV 2] 후보키 (파이썬/python)

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

코딩테스트 연습 - 후보키

 

이렇게 오른쪽으로 90도 회전하면 인덱스 하나로 속성값들의 집합을 인덱스 하나로 컨트롤할수있어서 

일단 오른쪽으로 90도 회전시킴

 

그 후 조합을 이용해서 어떤 속성값들을 사용할지 뽑아낸다.

속성이 1 2 3  이 있다면 더 많이 뽑는것부터 적게뽑는순으로 조합을 뽑음

 

1 2 3

1 2

1 3 

2 3

1

2

3

이렇게!

 

각 속성의 집합들을 set을 사용해 중복검사해서 유일성을 충족하는지 확인!

그 후 result_list 에 기존에 들어가있던 후보들과 비교해서

최소성을 충족할 수 있는지를 확인한다.

 

이렇게 하면 유일성과 최소성을 검사할 수 있고

result_list의 len값이 최종 답이 된다!

 

 

from itertools import combinations
 
 
def solution(relation):
    answer = 0
    result_list = []
 
    # 효율적인 컨트롤을 위해 행렬 돌려줌
    rel_list = [[relation[i][j] + str(j) for i in range(len(relation) - 1, -1, -1)] for j in range(len(relation[0]))]
 
    for i in range(len(relation[0]), -1, -1):
        search_list = [''] * len(relation)
 
        combi = list(combinations(rel_list, i))
        for com in combi:
            for c in com:
                for j in range(len(c)):
                    search_list[j] += c[j] + " "
            # 중복 없앴는데 길이가 유지되면 유일성 가능
            if len(set(search_list)) == len(relation) and result_list:
                idx = []
                for k in range(len(result_list)):
                    a_list = search_list[0].split(" ")
                    b_list = result_list[k][0].split(" ")
                    cnt = 0
                    for a in a_list:
                        # 그 문자열이 없으면 들어갈 수 있다는 뜻
                        if a in b_list:
                            cnt += 1
 
                    if cnt == len(a_list):
                        idx.append(result_list[k])
                for _ in idx:
                    result_list.remove(_)
                result_list.append(search_list)
 
            elif len(set(search_list)) == len(relation) and not result_list:
                result_list.append(search_list)
 
            search_list = [''] * len(relation)
 
    return len(result_list)