[2019 KAKAO BLIND RECRUITMENT] 후보키 - Python

[문제 이해 및 풀이]

후보키가 될 수 있는 수는 1개부터 relation의 column수까지 가능하다.

column의 수를 받아와 조합(combination)을 만들어주어 후보키가 될 수 있는 후보들을 combi에 저장해두었다.

 

combi에 저장해둔 후보들을 한번씩 돌면서 그 값에 해당하는 변수들을 뽑아 튜플형태로 lst에 저장해주었다.

튜플형태로 저장하지 않을 경우에는 set()을 사용할 때 원하는 결과를 얻을 수 없기 때문에 같은 인덱스로 묶인 값끼리 함께 처리될 수 있도록 하기 위해서 튜플이 필요하다.

 

lst에 저장된 값과 lst에 set을 적용한 것의 길이가 같을 경우는 유일성이 만족되므로 flag를 True로 설정해주었다.

flag가 True은 경우에는 해당하는 인덱스의 값을 check리스트에 추가해주었다.

 

이렇게만 짜면 0일때와 0,1일때 모두 check리스트에 들어가게 된다. 이 경우는 최소성을 만족하지 못하므로 check리스트에 있는 값들 중 하나가 지금 for문을 돌고있는 idx의 subset이라면 flag를 False로 설정하여 check리스트에 들어가지 못하도록 하였다.

---

[나의 코드]

from itertools import combinations
def solution(relation):
    n=len(relation[0])
    combi=[]
    for i in range(1,n+1):
        combi+=combinations(range(n),i)
    check=[]
    for idx in combi:
        flag=False
        lst=[]
        for person in relation:
            a=[]
            for i in idx:
                a.append(person[i])
            lst.append(tuple(a))
        if len(set(lst))==len(relation):
            flag=True
            
        for c in check:
            if set(c).issubset(idx):
                flag=False
                break
        
        if flag==True:
            check.append(idx)
    return len(check)

 

---

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키