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

# 후보키
from itertools import combinations


def solution(relation):
    answer = 0
    N, M = len(relation), len(relation[0])
    arr = []
    for i in range(1, M+1):
        arr.extend(combinations(range(M), i))

    total = []
    for x in arr:
        isOK = True
        for t in total:
            for k in t:
                if k in ''.join(map(str, x)):
                    isOK = False
                else:
                    isOK = True
                    break
            if not isOK:
                break
        if isOK:
            if check(x, relation):
                total.append(list(map(str, x)))
                answer += 1
    return answer


def check(arr, relation):
    isOK = True
    temp = []
    for j in range(len(relation)):
        str = ''
        for i in arr:
            str += relation[j][i]
        if str not in temp:
            temp.append(str)
        else:
            isOK = False
            break
    if isOK:
        return True
    return False

 

2019 카카오 블라인드 - 3번

1. combination을 이용해서 모든 경우의 수를 구한다. (후보키로 사용할 키의 인덱스 값으로)

2. 전체 경우에 수에 대해서 total(등록된 후보키)가 현재 후보키에 포함 여부를 검사한다. (최소성)

3. 현재 후보키가 최소성이 보장된다면 check함수로 유일성을 만족하는지 체크한다. (유일성)

    - 해당 키 인덱스 값들을 문자열로 합해서 겹치는 값이 있는지 없는지 검사

4. 유일성을 만족하면 total에 해당 후보키를 append하고 answer += 1

5. answer 출력

 

 

삽질을 해서 한시간이나 걸렸다...

for k in t:
        if k in ''.join(map(str, x)):
                isOK = False
        else:
                isOK = True
                break

여기서 total의 후보키(t)의 각 요소(k)마다 현재 경우의 수와 비교하는 이유는

예로 들어서 후보키가 '02' 이면 '023'도 체크하고 '012'도 체크할 수 있기 때문이다.

각 요소마다 체크를 하지 않으면 '02'는 '012'에 포함이 안되기 때문