[프로그래머스/Python] 후보키(조합/비트연산)

코딩테스트 연습 - 후보키

 

1. 조합

 

from itertools import combinations
from collections import Counter

def makeTuple(lists, tuples):
    # lists: 튜플로 변환할 리스트
    # tuples: (몇개씩 묶어서 튜플로 만들 것인지)
    tmp = []
    for i in tuples:
        tmp.append(lists[i])
    return list(map(tuple, zip(*tmp)))


def isSub(a, b):
    # a: b에 있는지 없는지 찾아야 된다.
    # b: tuple
    cnt = 0
    for i in a:
        if i in b:
            cnt += 1
    
    if cnt==len(a):
        return True
    else:
        return False
    
    
def solution(relation):
    answer = 0
    
    transpose = list(map(list, zip(*relation)))
    num = len(transpose)
    arr = [i for i in range(num)]
    
    # 모든 조합 만들기
    combis = []
    for j in range(1,num+1):
        combis += list(combinations(arr, j))

    
    # 모든 조합을 돌면서 아닌 조합 빼기 -> 모든 조합 다 빼면 끝
    while combis:
        
        combi = combis.pop(0)
        arr_tmp = makeTuple(transpose, combi)
        dict_tmp = Counter(arr_tmp)
        
        flag = 1
        for i in dict_tmp:
            if dict_tmp[i] != 1:
                flag = 0
            
        if flag == 1: #후보키이면 후보키가 포함된 애들 combi에서 지운다.
            answer += 1
            idx = []
            for j in combis:
                if isSub(combi, j):
                    idx.append(j)     
            for j in idx:
                combis.remove(j)

    
    return answer

 

2. 비트연산

 

def solution(relation):
    answer = []
    for i in range(1, 1<<len(relation[0])): #모든 조합에 대한 검사
        
        not_duplicate = True
        for num in answer:
            if num & i == num:
                not_duplicate = False
                break
        
        if not_duplicate:
            tmp_set = set()
            for j in range(len(relation)): #모든 사람을 돌면서
                tmp = ""
                for k in range(len(relation[0])): #모든 key에 대해
                    if i & (1<<k):
                        tmp += str(relation[j][k])
                tmp_set.add(tmp)
            
                if len(tmp_set) == len(relation):
                    answer.append(i)
    
    return len(answer)