46. 후보키

후보키
2019 KAKAO BLIND RECRUITMENT
1798명 완료

풀이 자체는 어렵지 않으나, 
파이썬에서 zip의 사용법을 모르면
코딩이 조금 까다롭다. 

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

코딩테스트 연습 - 후보키

머리는 적게 쓰고 컴퓨터를 많이 쓰는
훌륭한(?) 전수조사(brute force) 알고리듬을 만들자. 

나의 머리는 소중하니까..
많이 부려먹으려고 비싼 컴퓨터 산 거 아님?

각 칼럼의 조합 즉 nCr을 r = 1 ~ len(relation)까지 만들고.. 

각 조합의 유일성을 확인하고.. 
(파이썬에는 딕셔너리나 집합을 사용하면 편하다..)

유일성을 통과한 조합을 A,
유일성과 최소성 확인을 이미 통과한 조합들을 B 라할 때 
B는 A의 부분 집합이 아니어야 한다. 

그런데 zip의 사용법을 잊어버려서 한참을 헤맸다...
8개월 만에 코딩이라..
zip함수를 만들까까지 고민했다.

list 2개를 인자로 넣으면 잘 작동된다. 

list(zip([1, 2, 3], [4, 5, 6]))
[(1, 4), (2, 5), (3, 6)]

list 2개를 1개의 list로 묶어서 zip에 보내면 작동하지 않는다 ㅠ,.ㅠ 

list(zip([[1, 2, 3], [4, 5, 6]]))
[([1, 2, 3],), ([4, 5, 6],)]

이럴 때 *를 이용하면 포장을 하나 벗겨준다.. 

list(zip(*[[1, 2, 3], [4, 5, 6]]))
[(1, 4), (2, 5), (3, 6)]

이제 떠올랐으니 일사천리 코딩....

def solution(relation):
    from itertools import combinations
    r = [tuple(each) for each in zip(*relation)]
    combies = [combi for i in range(len(r)) for combi in combinations(r, i + 1)]
    candidate_keys = []
    for combi in combies:
        zip_elements = list(zip(*combi))
        if len(zip_elements) == len(set(zip_elements)):  # 유일성 확인
            for candidate_key in candidate_keys:  # 최소성 확인. 지저분...
                for element in candidate_key:
                    if element not in combi:
                        break
                else:  # 브레이크가 없었다 = 모든 원소가 다 들어 있었다 = 최소성에서 탈락
                    break  # 탈락한 분들은 브레이크
            else:
                candidate_keys.append(combi)
    return len(candidate_keys)

일단 이렇게 풀어봤는데... 최소성 확인하는 부분이 좀 지저분...

11번 테스트 케이스에서 걸려 버렸다.. 
11번이 이런 케이스가 아닐까?

[["a", "a"], ["b", "b"]]  # 2 가 나와야 하는데 1 이... 

1번 2번 컬럼 모두 고유 키로 사용해도 되지만 위 코드에서는 이를 중복으로 본다.. 

예를 들자면 이름과 전공이 art 인 사람.
이름과 전공이 music 인 사람이 있을 때,
이름을 고유 키로, 전공을 고유 키로 해도 된다.. 

그래서 직접 비교하지 않고 인덱스를 이용하도록 코드를 고쳤다.. 
지저분한 부분도 같이 수정.

def solution(relation):
    from itertools import combinations
    r = [tuple(each) for each in zip(*relation)]
    combies = [set(combi) for i in range(len(r)) for combi in combinations(range(len(r)), i + 1)]
    candidate_keys = []
    for combi in combies:  # combi에는 (실제 원소?가 아닌) 숫자 인덱스의 조합만 들어있다..
        elements = [r[index] for index in combi]  # 실제 (원소?들의) 조합을 만들기 위해서 리스트를 하나..
        zip_elements = list(zip(*elements))
        if len(zip_elements) != len(set(zip_elements)):  # 유일성 테스트
            continue
        for candidate_key in candidate_keys:  # 최소성 테스트
            if candidate_key.intersection(combi) == candidate_key:
                break
        else:
            candidate_keys.append(combi)
    return len(candidate_keys)

테스트 1 〉	통과 (0.07ms, 10.8MB)
테스트 2 〉	통과 (0.08ms, 10.7MB)
테스트 3 〉	통과 (0.08ms, 10.6MB)
테스트 4 〉	통과 (0.08ms, 10.8MB)
테스트 5 〉	통과 (0.10ms, 10.7MB)
테스트 6 〉	통과 (0.05ms, 10.9MB)
테스트 7 〉	통과 (0.05ms, 10.8MB)
테스트 8 〉	통과 (0.05ms, 10.6MB)
테스트 9 〉	통과 (0.09ms, 10.8MB)
테스트 10 〉	통과 (0.11ms, 10.8MB)
테스트 11 〉	통과 (0.13ms, 10.8MB)
테스트 12 〉	통과 (0.62ms, 10.6MB)
테스트 13 〉	통과 (0.20ms, 10.8MB)
테스트 14 〉	통과 (0.08ms, 10.7MB)
테스트 15 〉	통과 (0.07ms, 10.7MB)
테스트 16 〉	통과 (0.08ms, 10.7MB)
테스트 17 〉	통과 (0.08ms, 10.7MB)
테스트 18 〉	통과 (1.06ms, 10.7MB)
테스트 19 〉	통과 (0.70ms, 10.7MB)
테스트 20 〉	통과 (1.15ms, 10.6MB)
테스트 21 〉	통과 (0.82ms, 10.9MB)
테스트 22 〉	통과 (0.62ms, 10.8MB)
테스트 23 〉	통과 (0.09ms, 10.7MB)
테스트 24 〉	통과 (0.74ms, 11MB)
테스트 25 〉	통과 (1.00ms, 10.8MB)
테스트 26 〉	통과 (0.84ms, 10.9MB)
테스트 27 〉	통과 (0.19ms, 10.5MB)
테스트 28 〉	통과 (0.20ms, 10.7MB)

다행히 통과...