[programmers] 후보키

---

로직

1. 우선 가능한 열의 조합을 모두 만든다(itertools.combination)

2. 각각 유일하게 식별이 가능한지 확인한다. (unique함수 사용)

3. 유일한 것들 중에 최소성을 만족하는 것만 남긴다 -> 부분집합 사용

 

코드

from itertools import combinations
from copy import deepcopy

def solution(relation):
    def unique(row, co):
        check = []
        for item in relation:
            check.append(tuple(item[idx] for idx in co))

        if len(set(check)) == row:
            return True

        return False

    row = len(relation)
    column = len(relation[0])
    columns = [i for i in range(column)]

    use = []
    for i in range(1, column + 1):
        comb = list(combinations(columns, i))
        for co in comb:
            if unique(row, co):
                use.append(co)

    visit = [0] * len(use)
    for i in range(len(use)):
        for j in range(i + 1, len(use)):
            if set(use[i]).issubset(set(use[j])):
                visit[j] = 1

    cnt = 0
    for i in visit:
        if i == 0:
            cnt += 1

    return cnt

 

주의할 점

1. 부분집합 구하는 방법

     1) set(a).issubset(set(b))

     2) use[i] == use[i] & use[j]: -> 이렇게 써라!!

2. [중복 확인 방법]

    1) issubset을 사용해(only set일때 사용가능) -> set(use[i])가 set(use[j])의 부분집합이 된다면 지워라!
         ** 문제점 : 지우면 index가 달라져서 에러,,
         ** 해결책 : use를 deepcopy한 후 지운다.

    2) visit으로 확인하고 방문하지 않은 애들만 갯수를 센다 0 -> 현재 내가 사용한 방법

 

3. 유일하게 식별 가능한지 확인하는 unique함수

     ** 문제점 : use = [('1', '0', '0', 'r', 'y', 'a', 'n'), ('2', '0', '0'), ('3', '0', '0'), ('4', '0', '0'), ('5', '0', '0'), ('6', '0', '0')]로 나온다

           내가 필요한 것은 use = [('100', 'ryan', 'music'), ('200', 'apeach', 'math'), ('300', 'tube', 'computer'), ('400', 'con', 'computer'), ('500', 'muzi', 'music'), ('600', 'apeach', 'music')]

check = []
for item in relation:
	for idx in co:
		check.append(tuple(item[idx]))
		use.append(co)

     ** 해결책

check = []
for item in relation:
	check.append(tuple(item[idx] for idx in co))

 

4. ** 문제점 : 유일성과 최소성을 한번에 구별하려했다.

use = []
check = []  # [('100', 'ryan', 'music'), ('200', 'apeach', 'math'), ('300', 'tube', 'computer'), ('400', 'con', 'computer'), ('500', 'muzi', 'music'), ('600', 'apeach', 'music')]
for item in relation:
	check.append(tuple(item[idx] for idx in co))

	if co not in use:
		use.append(co)
print(use)

이렇게 식을 작성해버리면 use에 쌓이지 않고 [(0,)], [(1,)], [(2,)], [(3,)], [(0, 1)]이런 식으로 나와버린다.

    ** 해결책 : unique에 해당하는 use를 다 넣어버리고나서 나중에 중복이 있는지 확인한다. -> 최종채택