[programmers/Lv.2] 후보키

❓  문제

2019 KAKAO BLIND RECRUITMENT - 후보키

 

🛎️  아이디어

1. 후보키가 될 수 있는 집합을 만든다.
    a. relation의 컬럼(column) 숫자를 가지고 만든다.
    b. 해당 결과는 (0), (1), ... (0, 1), (0, 2), ... (0, 1, 2, 3) 으로 나온다.

2. 만든 집합을 돌면서 해당 인덱스에 맞는 값들을 가지고 실제 집합을 만들어 준다.

3. 실제 집합 상태에서 중복 제거를 해준다.
      a. 유일성을 만족하는지 확인하기 위함이다.

4. 유일성을 만족한다면 (중복 제거 후에도 relation의 row길이와 같다면) 
      a. answer 배열에 해당 인덱스 집합의 부분집합이 있는지 확인한다.
      b. 예를 들어, (0, 1)은 (0)을 포함하기 때문에 최소성을 만족하지 않는다.
      c. 부분집합에 해당하지 않으면 answer 배열에 해당 인덱스 집합을 더해준다.

 

💻  풀이

from itertools import combinations

def solution(relation):
    
    # 가능한 인덱스 조합
    index_combination = []
    for r in range(1, len(relation[0]) + 1):
        index_combination.extend(combinations(range(len(relation[0])), r))
        
    answer = []
    for comb in index_combination:
        
        # 해당 인덱스를 사용한 실제 조합
        tmp1 = []
        for r in relation:
            tmp2 = []
            for c in comb:
                tmp2.append(r[c])
            
            # 이후에 2차원 중복제거를 위해 tuple로 변환 후 append
            tmp1.append(tuple(tmp2))
        
        # 유일성 확인
        if len(set(tmp1)) == len(relation):
            # 최소성 확인
            check = True
            for a in answer:
                if set(a).issubset(comb):
                    check = False
                    break
        
            if check: answer.append(comb)
    return len(answer)

 

🧩  포인트

- 2차원 리스트를 중복제거 하기 위해서는 tuple을 사용해 1차원 리스트로 만들어 주고 set을 사용한다.
- tuple은 중복 제거가 되지 않는다.