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

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

프로그래머스

 

1. 코드

---

      

      

      

    
    

      <python />
    
from itertools import combinations
from collections import defaultdict
def solution(relation):
    answer = 0
    column, row = len(relation[0]),len(relation)
    dic = defaultdict(int)
    
    for i in range(1,column+1): #1 컬럼개수
        for x in combinations(range(column),i): #2 컬럼조합
            
            status = 0 #5 최소성 검사
            for h in range(1,len(x)):
                for y in combinations(x,h):
                    if dic[y]:
                        status = 1
                        break
            if status:
                continue
                
            res =[]
            for r in relation: #3 모든 로우 탐색
                tmp = [r[j] for j in x]
                if tmp not in res:
                    res.append(tmp)
                    
            if len(res) == row: # 유일성 검사
                dic[x] = 1
                answer += 1
                
    return answer

 

2. 풀이

---

 

컬럼의 길이가 8, 로우의 길이가 20으로 알고리즘 문제들 사이에서는 상당히 작은 크기라고 생각이 들었고 모든 경우를 완전탐색하여 구현해도 시간복잡도가 별로 크지 않을 것이라 판단하였다.

 

내가 유일성과 최소성을 만족시킨 방법은 다음과 같다.

• 유일성
  • 조합할 속성의 개수를 1개부터 속성의 개수만큼 하나씩 늘린다.
  • combinations를 통해 속성들을 개수만큼 조합한다. 
  • 조합을 모두 저장하는데 만약 조합이 중복이 된다면 후보키가 되지 않고 중복이 없다면 후보키로 인정한다.
• 최소성
  • 이미 후보키인 조합을 포함하고 있다면 후보키로서 인정될 수 없다.
  • combinations를 사용하여 조합안에서 또 조합을 추려내고 이미 후보키인 조합이 있다면 후보키로 인정하지 않는다.
  • defaultdict를 사용하여 조합을 키로 설정하고 후보키가 되면 1로 바꿔주었다.
  • 유일성보다 먼저 검사하여 시간복잡도를 줄인다.