[프로그래머스] 후보키 (파이썬 풀이)

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

코딩테스트 연습 - 후보키

 

내 풀이:

from itertools import combinations as co

def solution(relation):
    row_size, col_size = len(relation), len(relation[0])
    ans = []
    # 가능한 모든 열들의 인덱스 조합을 각 행에 대입
    for c in range(1, col_size + 1):
        for col in co(range(col_size), c):
            check = []
            for row in relation:
                temp = []
                for idx in col:
                    temp.append((row[idx]))
                check.append(tuple(temp))

            # 유일성 체크
            if len(set(check)) == row_size:
                if any([set(col).issuperset(set(a)) for a in ans]):
                    continue
                # 최소성 체크
                else:
                    ans.append(col)       

    return len(ans)

• 아이디어: 후보키가 될 수 있는 모든 인덱스 조합에 대해 유일성과 최소성 확인하면서 정답 리스트에 추가
• 최소성 구현하는데 꽤 오래 걸림 (부분집합 생각 안났음)

참고 풀이:

def solution(relation):
    answer_list = list()
    # 비트연산으로 모든 조합 표현
    for i in range(1, 1 << len(relation[0])):
        tmp_set = set()
        for j in range(len(relation)):
            tmp = ''
            for k in range(len(relation[0])):
                if i & (1 << k):
                    tmp += str(relation[j][k])
            tmp_set.add(tmp)

        if len(tmp_set) == len(relation):
            not_duplicate = True
            for num in answer_list:
                if (num & i) == num:
                    not_duplicate = False
                    break
            if not_duplicate:
                answer_list.append(i)
                
    return len(answer_list)

• 아이디어는 완전 동일하나, 라이브러리 사용하지 않고 비트 연산을 이용해 모든 조합의 경우 표현