파이썬 알고리즘 : 후보키
2024년 5월 24일 알고리즘 문제풀이 문제 후보키 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 from itertools import combinations # 최소성을 만족하는지 확인하는 함수 # 검증하는 조합 target의 부분집합이 이미 찾은 조합 answer_array에 포함되어 있는지 확인 # 포함되어 있으면 target은 최소성을 만족하지 않음 def validate(answer_array,target): for i in answer_array: if set(i).issubset(target): return False return True def solution(relation): answer = [] n = len(relation) m = len(relation[0]) arr = [ i for i in range(m)] for i in range(m): # 모든 속성 조합을 구함. idx = list(combinations(arr,i+1)) for q in idx: # 유일성을 만족하는지 확인 # 속성의 값을 이은 문자열을 set에 넣어 중복을 제거 # 중복이 없다면 유일성을 만족 check = set() for j in range(n): tmp = "" for k in q: tmp += relation[j][k] check.add(tmp) # set의 길이가 n과 같다면 중복이 없단 의미로 유일성을 만족 if len(check) == n: # 최소성을 만족하는지 확인 if validate(answer,q): answer.append(q) return len(answer)