후보키 [프로그래머스]

문제풀이

이건 일단 "어떤 컬럼을 써서 후보키를 만드는지" 가 관건이다.

어떤 컬럼을 사용해야 하는지 모르기 때문에 더할 컬럼들 (0번 컬럼 + 1번 컬럼 등)의 후보를 만드는게 첫번째다.

또한 중복이 없어야 하며, 더하는 컬럼의 순서가 중요하지 않다.

(0번 컬럼 + 1번 컬럼) 을 이용해 키를 만들어 구분하나 (1번 컬럼 + 0번 컬럼) 을 만들어 구분하나 똑같다.

index 값을 이용해 더할 컬럼의 후보를 만들어 준다.

com_len = len(relation[0])
    
from itertools import combinations # 중복이 없는 후보군들 반환 하기 위한 combination 임포트
com_list = []
index_list = [i for i in range(com_len)]
for i in range(1,com_len+1): # 개수를 늘려가면서 combination 값들을 com_list에 추가
    combi = combinations(index_list,i)
    com_list.extend(combi)

#ex. [(0,), (1,), (2,), (3,), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3), (0, 1, 2, 3)]

 

해당 combination (더할 컬럼 후보군)을 순회 하면서 해당 컬럼으로 만든 set이 기존에 들어온 값과 길이가 같다면 answer += 1 해준다.

주의 할 점은 후보키는 최소가 되야 한다는 조건이다. 0번 컬럼으로 모든 relation을 구분할 수 있다면, 0번 컬럼이 포함된 후보군은 제외 되어야 한다.

remove_index_list = []
flag = False
for indexs in com_list: # 더할 컬럼들을 순회
    for remove_index in remove_index_list: #0번이 후보키라면 (0,1) 후보키는 볼 필요x
        if set(remove_index).issubset(set(indexs)):
            flag = True
            break
        
    if flag:
        flag = False
        continue
    
    temp_set = set()
    #print(indexs)
    for r in relation:
        temp_string = ""
        for i in indexs: 
            temp_string += r[i]+"@"
        temp_set.add(temp_string)
    #print(temp_set, len(temp_set))
    if len(temp_set) == len(relation): # 후보키로 구분된 값과 기존 값의 길이가 같다면(구분성공)
        answer+=1 
        remove_index_list.append(indexs) # 최소 후보키 값으로 등록

 

완성 코드

def solution(relation):
    answer = 0
    
    com_len = len(relation[0])
    
    from itertools import combinations
    com_list = []
    index_list = [i for i in range(com_len)]
    for i in range(1,com_len+1):
        combi = combinations(index_list,i)
        com_list.extend(combi)
    
    #print(com_list)
    remove_index_list = []
    flag = False
    for indexs in com_list:
        for remove_index in remove_index_list:
            if set(remove_index).issubset(set(indexs)):
                flag = True
                break
            
        if flag:
            flag = False
            continue
        
        temp_set = set()
        #print(indexs)
        for r in relation:
            temp_string = ""
            for i in indexs:
                temp_string += r[i]+"@"
            temp_set.add(temp_string)
        #print(temp_set, len(temp_set))
        if len(temp_set) == len(relation):
            answer+=1 
            remove_index_list.append(indexs)
    
    return answer

 

문제는 여기

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

코딩테스트 연습 - 후보키