[프로그래머스] 후보키 - python

후보키

문제

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

풀이

순위 검색 문제와 비슷했다. 언패킹 몰랐으면 풀기 어려웠을 것 같다.

가능한 모든 키 조합을 구한 다음에 카운터로 튜플 개수가 모두 1개 인 것을 찾는다.

일단 행, 열을 바꾸면 중복을 확인하기 쉬울 것 같아서 행, 열을 바꿔서 속성 별로 묶었다.

1개씩 후보키인지 확인하고 후보키인 것은 제외한 후 나머지 키로 조합을 구했다.

2개 선택했을 때부터 n개 선택했을 때까지 조합을 구한다.

 

유일성 확인

• 속성 1개일 때: 중복 제거 후 원래 배열과 길이가 같은지 본다.
• 그외 : 해당 하는 속성들을 다시 행으로 묶어서 Counter 한 후 2개 이상인 행이 있는지 확인한다.

최소성 확인

• 조합에서 한 개씩 제거해 본 후 제거한 키 조합이 하나라도 유일성을 만족하는지 확인한다.
• 하나라도 만족한다면 최소성을 만족하지 못하므로 False를 리턴한다.

from itertools import combinations
from collections import Counter


# 최소성 확인
def check_minimality(case, col):
    for x in range(len(case)):
        tmp = list(case)
        tmp.remove(case[x])
        
        if check_uniqueness(tmp, col):
            return False
    return True

# 유일성 확인
def check_uniqueness(case, col):
    tuples = []
    for c in case:
        tuples.append(col[c])

    tuples = [tuple(i) for i in zip(*tuples)]
    return Counter(tuples).most_common()[0][1] == 1
    
def solution(relation):
    answer = 0
    col = [list(i) for i in zip(*relation)] # 행, 열 바꾸기
    keyIdx = [i for i in range(len(relation[0]))]
    
    # 1개일 때 유일성 확인 후 제외
    for i, c in enumerate(col):
        if len(set(c)) == len(c): # 중복 제거하고 나서도 길이가 같은지?
            answer += 1
            keyIdx.remove(i)
            
    # 나머지 조합 확인
    for i in range(2, len(keyIdx) + 1):
        for case in combinations(keyIdx, i):
          	# 유일성, 최소성 만족하면 +1
            answer += int(check_minimality(case, col) and check_uniqueness(case, col))
                    
                    
                
    return answer