[카카오 기출] 후보키

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

코딩테스트 연습 - 후보키

 

왤케 오래걸리고 어려웠을까..

일단 버벅인 원인 중 하나가 for문을 너무 여러번 쓰다보니 내가 쓴 것마저 헷갈렸다는 것.

리스트 컴프리헨션을 잘 활용해야 코드 양도 줄고 이해도 더 쉬워질 것 같다.

 

 

<처음 통과 코드>

import collections
import itertools

def solution(relation):
    def isSub(small, big):        
        if len(list(set(big)|set(small))) == len(big):
            return True
        else:
            return False
    
    col = len(relation)
    row = len(relation[0])
    key = []
    dct = collections.defaultdict(int)
    
    lst = [x for x in range(row)]
    answer = 0
    for i in range(1, row+1):
        com_lists = list(itertools.combinations(lst, i))
        for com in com_lists:       
            stop = False
            for c in key:
                if isSub(c, com):     
                    stop = True
                    break

            if stop:
                continue

            for n in range(col):
                dct_key = ""
                for j in range(len(com)):
                    dct_key += (str(com[j]) + relation[n][com[j]])
                dct[dct_key] += 1
                if dct[dct_key] > 1:
                    stop = True
                    break
            if not stop:
                key.append(com)
                answer += 1
    
    return answer

 

<개선 코드 1>

issubset 메소드 사용 -> 따로 함수 만들 필요가 없었음

모든 조합의 경우를 리스트로 저장해 놓음 -> 반복문 하나 줄일 수 있음

import collections
import itertools

def solution(relation):
    col = len(relation)
    row = len(relation[0])
    key = []
    dct = collections.defaultdict(int)
    
    answer = 0
    
    candidates= []
    for i in range(1, row+1):
        candidates.extend(itertools.combinations(range(row), i))       
    
    for com in candidates:       
        stop = False
        for c in key:
            if set(c).issubset(set(com)):     
                stop = True
                break

        if stop:
            continue

        for n in range(col):
            dct_key = ""
            for j in range(len(com)):
                dct_key += (str(com[j]) + relation[n][com[j]])
            dct[dct_key] += 1
            if dct[dct_key] > 1:
                stop = True
                break
        if not stop:
            key.append(com)
            answer += 1
    
    return answer

 

 

<개선 코드 2>

dct_key 만드는 부분도 리스트 컴프리헨션으로 간결하게 수정

import collections
import itertools

def solution(relation):
    col = len(relation)
    row = len(relation[0])
    key = []
    dct = collections.defaultdict(int)
    
    answer = 0
    
    candidates= []
    for i in range(1, row+1):
        candidates += list(itertools.combinations(range(row), i))
    
    for com in candidates:       
        stop = False
        for c in key:
            if set(c).issubset(set(com)):     
                stop = True
                break
        if stop:
            continue

        for n in range(col):
            dct_key = tuple([relation[n][x]+str(x) for x in com])
            dct[dct_key] += 1
            if dct[dct_key] > 1:
                stop = True
                break
        if not stop:
            key.append(com)
            answer += 1
    
    return answer

 

 

<개선 코드 3>

내친김에 후보키의 최소성을 살펴보는 부분(16째줄)도 리스트 컴프리헨션을 써봤다.

근데 이건 리스트에 True가 나오는 즉시 중단을 하는 게 아니라서 성능은 개선2보다 떨어질 수 밖에 없다. 

import collections
import itertools
def solution(relation):
    col = len(relation)
    row = len(relation[0])
    key = []
    dct = collections.defaultdict(int)
    
    answer = 0
    
    candidates= []
    for i in range(1, row+1):
        candidates += list(itertools.combinations(range(row), i))
    
    for com in candidates:
        if True in [set(x).issubset(set(com)) for x in key]:
            continue

        stop = False
        for n in range(col):
            dct_key = tuple([relation[n][x]+str(x) for x in com])
            dct[dct_key] += 1
            if dct[dct_key] > 1:
                stop = True
                break
        if not stop:
            key.append(com)
            answer += 1
    
    return answer