[프로그래머스] Level 2 - 후보키 (Python)

 

 

 

 

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

코딩테스트 연습 - 후보키

 

 

 

 

✅ Solution

• combinations를 이용해 가능한 후보키 조합을 모두 구한다.
• 해당 배열을 돌면서 유일성, 최소성을 확인한다.
  • 유일성 : 후보키 조합에 따라 relation을 돌면서 값들을 tuple 형태로 저장한 뒤, set(tuple)의 길이가 relation의 row 수랑 같으면 각자 유일한 값을 가지고 있다는 뜻
  • 최소성 : 유일성을 만족하는 조합 중 이미 unique 배열에 들어간 값들이 해당 조합의 부분집합인지 확인, 만약 부분집합이라면 최소성을 만족하지 못한다는 뜻

 

 

 

✅ Code

from itertools import combinations

def solution(relations):
    row, col = len(relations), len(relations[0])
    candidates = []

    for i in range(1, col + 1):
        candidates.extend(combinations([x for x in range(col)], i))

    unique = []
    for candidate in candidates:
        temp = [tuple([relation[i] for i in candidate]) for relation in relations]

        if len(set(temp)) == row:
            check = True
            for u in unique:
                if set(u).issubset(set(candidate)):
                    check = False
                    break
            if check:
                unique.append(candidate)

    return len(unique)

 

 

 

📝 Today I Learned

set

• issubset() -> 부분 집합인지 아닌지 True, False 반환