[파이썬] 카카오 코테 - 후보키

1. 기본적으로 subset 찾기 문제를 잘 구현해야 한다.
   dfs 또는 비트마스킹으로 할 수 있는데 dfs가 외워두면 여러모로 쓸모가 많다. python 내장 함수인 itertools.combination이 편하고 좋지만 경우에 따라서 dfs를 쓰는게 좋을 때도 있었다. 개인적으로 bitmasking 이 젤 좋지만 dfs가 사용성을 고려하면 젤 가성비가 좋다. (조합, 순열, subset 등..) 코드에서 특히 uniqueness 조건을 dfs안에다가 넣어서 사용하면 조금 더 시간을 절약할 수 있다. (비트마스킹이나 combinations에서도 가능..)

2. minimality 구현은 Set 객체의 메써드인 issubset()을 사용했다. 위에서 사용한 부분집합을 그대로 사용해도 되지만 연습삼아서 subset을 사용해보았다. 코드가 더 짧아진다. 이 부분을 놓쳐서 자력으로 못 풀었다. 아마도 이 문제가 lv2인 것은 이 부분 때문일 것이다.

3. minimality를 연산하는 단계는 모든 가능한 키 조합을 다 끄집어 낸 다음이다. uniqueness와 달리 중간에는 어떻게 해도 minimality를 판별할 수 없었다.

from collections import Counter, defaultdict


def minimality(result):
    answer = []

    for x in result:
        flag = False
        for y in result:
            if x == y:
                continue
            else:
                if set(y).issubset(set(x)):
                    flag = True
                    break
        if flag:
            continue
        answer.append(x)
    return answer


def check_unique(relation, candidate):
    if len(candidate) == 0:
        return False
    keys = defaultdict(int)
    for row in relation:
        key = ''.join([row[cand] for cand in candidate])
        keys[key] += 1
        if keys[key] >= 2:
            return False
    return True


result = []


def mycombinations(arr, path, result, index, relation):
    if len(path) > 0 and check_unique(relation, path[:]):
        result.append(path[:])
        path[:].pop()
        return
    for i in range(index, len(arr)):
        path.append(arr[i])
        mycombinations(arr, path, result, i + 1, relation)
        path.pop()


def solution(relation):
    cands = [i for i in range(len(relation[0]))]
    mycombinations(cands, [], result, 0, relation)
    print(result)
    answer = minimality(result)
    print(answer)
    return len(answer)

print(solution([["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]))