파이썬 프로그래머스 : 후보키

문제 

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

프로그래머스

 

 

풀이

• 알고리즘
  수 범위가 작아서 모든 경우의 수를 탐색했다. (부루트포스)
• 자료구조
  column별로 확인하는 것이 더 편리할 것 같아, relation을 전치했다.
  만족하는 조합의 결과(튜플)을 저장할 answer set을 정의했다. 

 

from itertools import combinations
def solution(relation):
    colum_num=len(relation[0])
    index=[i for i in range(colum_num)]
    answer=set()
    relation = list(map(list, zip(*relation))) #relation 전치
    
    for k in range(1,colum_num+1): #조합 계산 (범위에 주의)
        result=[]
        for comb in list(combinations(index,k)):
            is_subset=False #최소성 확인을 위한 변수 
            result=list(zip(*[relation[l] for l in comb]))
            
            if len(result)==len(set(result)): #겹치는게 없는 경우
                for l in answer:
                    if set(l).issubset(comb): #최소성의 확인
                        is_subset=True
                        break
                if is_subset==False:
                    answer.add(comb)
        

    return len(answer)

 

결과

테스트 1 〉	통과 (0.04ms, 10.1MB)
테스트 2 〉	통과 (0.05ms, 10MB)
테스트 3 〉	통과 (0.04ms, 10.1MB)
테스트 4 〉	통과 (0.04ms, 10.2MB)
테스트 5 〉	통과 (0.04ms, 10.1MB)
테스트 6 〉	통과 (0.01ms, 10.3MB)
테스트 7 〉	통과 (0.02ms, 10.2MB)
테스트 8 〉	통과 (0.02ms, 10.1MB)
테스트 9 〉	통과 (0.06ms, 10.1MB)
테스트 10 〉	통과 (0.09ms, 10.2MB)
테스트 11 〉	통과 (0.13ms, 10MB)
테스트 12 〉	통과 (0.86ms, 10.3MB)
테스트 13 〉	통과 (0.26ms, 10MB)
테스트 14 〉	통과 (0.04ms, 10.3MB)
테스트 15 〉	통과 (0.05ms, 10.2MB)
테스트 16 〉	통과 (0.04ms, 10.1MB)
테스트 17 〉	통과 (0.05ms, 10.1MB)
테스트 18 〉	통과 (1.18ms, 10.1MB)
테스트 19 〉	통과 (0.70ms, 10.3MB)
테스트 20 〉	통과 (1.21ms, 10.1MB)
테스트 21 〉	통과 (0.73ms, 10.2MB)
테스트 22 〉	통과 (0.71ms, 10.2MB)
테스트 23 〉	통과 (0.09ms, 10.2MB)
테스트 24 〉	통과 (0.79ms, 10.1MB)
테스트 25 〉	통과 (1.01ms, 10.3MB)
테스트 26 〉	통과 (0.75ms, 10.2MB)
테스트 27 〉	통과 (0.18ms, 10.2MB)
테스트 28 〉	통과 (0.16ms, 10.1MB)

 

 

덧) 

zip사용의 중요성..