[프로그래머스] 후보키

그냥 구현이 까다로웠던 문제이다... 이렇게 더럽게 풀어도 되나 싶었는데 그냥 더럽게 푸는게 맞았던 단순히 구현력을 물어보는 문제 같았다.

1. 문제 설명

테이블이 다음과 같이 있을때, 각각의 row를 유일하게 식별해줄 key를 고르는 문제이다.
이때 key는 2가지 조건을 만족해야 하는데 그 조건은 다음과 같다.

• 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
• 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

두 가지를 쉽게 직역하면 다음과 같다.

• 유일성 -> 하나의 row를 유일하게 식별해야 한다.
• 최소성 -> 하나의 row를 식별하는데 '학번'의 요소만 필요하다면 키는 '학번'으로만 하고, '학번'+'이름'으로 할 필요가 없다. 즉 개수를 최소한으로 하라는 것이다.

2. 어려웠던 점

1) 최소성을 만족시키는 것

이미 (1,2)가 나왔다면 (1,2,3)은 포함되지 말아야 한다. 이 부분을 만족시키는게 어려웠다기 보다는 ... 구현하기가 조금 번거로웠다.

3. 코드

from itertools import combinations

def check_is_in(already_key, new_key):
    if len(list(filter(lambda x:x in already_key, new_key))) == len(already_key):
        return False
    return True

def extract_minimize_key(minimize_part,reverse_relation):
    cnt =0
    result_compare = []
    
    for i in range(2,len(minimize_part)+1):
        confirm_key_num = combinations(minimize_part,i)
        for key_pair in confirm_key_num:
            is_pass = True
            for key_pair_compare in result_compare:
                if not check_is_in(key_pair_compare, key_pair):
                    is_pass = False
                    break
            if not is_pass:
                continue
            target_key_list = list(zip(*(reverse_relation[num] for num in key_pair)))

            for key_list in target_key_list:
                if target_key_list.count(key_list)>1:
                    break
            else:
                result_compare.append(key_pair)
                cnt +=1
    return cnt

def solution(relation):
    cnt = 0
    minimize_part = []
    reverse_relation = list(zip(*relation))

    for idx, val in enumerate(reverse_relation):
        for element in val:
            if list(val).count(element) > 1:
                minimize_part.append(idx)
                break
        else:
            cnt += 1

    if len(minimize_part) < 2:
        return cnt
    else:
        return cnt + extract_minimize_key(minimize_part, reverse_relation)

4. 기억해야 할 점

1) 애스터리스크

리스트가 있을때, 이 리스트를 90도 정도 돌려서 보여준다. 즉, 열 행을 바꾸는 것이다.
zip(*relation) -> 앞으로 많이 사용할 것 같다. 기억해두자 꼭 !