[프로그래머스] 42890 파이썬 - 후보키

풀이

문제에서 relation이라는 2차원 문자열 배열 안에 학생들의 인적사항이 주어진다.

인적사항의 column(열) 속성들에 대해, 유일성과 최소성을 만족하는 "후보키"를 구하는 문제이다.

 

 

다음과 같이 컬럼의 길이는 최대 8로 주어진다.

따라서 파이썬의 combinations를 사용하여 모든 컬럼의 조합을 구했다. 

(조합의 시간복잡도는 2 ^ 컬럼의 길이 = 256)

 

1. 모든 컬럼의 조합을 구한다.

2. 각 조합에 대해 유일성을 검사한다

    2-1. 집합(set()) 에 각 조합의 인덱스의 값들을 문자열로 변환한 값을 넣는다.

    2-2. 만약 해당 집합의 길이가 row의 길이와 같으면 겹치는 값이 없는 것이므로 유일하다.

3. 유일한 조합들을 모아놓은 candidate 리스트에 대해 최소성을 검사한다.

    3-1. 최소성을 만족한다는 것은 더 작은 조합으로 대체할 수 없는 것이다.

        => 예를 들어, 0이 이미 후보키이면 0을 가지는 집합들은 후보키가 될 수 없다.

    3-2. 따라서 candidate 리스트를 돌며 현재까지 확정된 후보키들을 부분집합으로 가지지 않는 값들을 찾는다. 찾았다면 확정된 후보키 리스트에 넣는다.

 

위와 같은 과정을 통해 답을 도출했다.

 

오늘 배운 것

A.issubset(B)

- A가 B의 부분집합인지 확인할 수 있다.

코드

from itertools import combinations

def solution(relation):
    row = len(relation)
    col = len(relation[0])
    
    # 인덱스 리스트
    indexs = [i for i in range(col)]
    candidate = []
    
    for i in range(1,col+1):
        # 속성들의 인덱스 조합을 뽑는다
        combi = combinations(indexs,i)
        
        for comb in combi:
            check = set()
            
            for r in relation:
                key = ""
                for c in comb:
                    key += r[c]
                check.add(key)
                
            # 유일성 체크
            if len(check) == row:
                candidate.append(comb)
                
    # 최소성 체크 (더 작은 조합으로 대체 X) => 0이 이미 후보키이면 0을 가지는 집합들은 후보키가 될 수 없다
    candidateKeys = []

    for cand in candidate:
        canBeKey = True
        
        for key in candidateKeys:
            if set(key).issubset(set(cand)):
                canBeKey = False
                break
                
        if canBeKey:
            candidateKeys.append(cand)

    return len(candidateKeys)

 

 

프로그래머스