수학과의 개발자 도전기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42890

Lv2 문제다!

풀이 아이디어는 쉽게 떠올랐는데, 이를 구현하는데 약간 번거로웠던 문제였다.

문제 이해 

후보키는 테이블 컬럼 중에 유일성과 최소성을 만족하는 컬럼 또는 컬럼의 집합을 의미한다.

유일성은 해당 컬럼 또는 집합으로 모든 튜플을 식별할 수 있어야 한다는 것이고

최소성은 (내가 이해한 바로는) 부분 집합으로도 모든 튜플을 식별할 수 있어야 한다는 것이다. 

유일성 원소를 구하는 건 어렵지 않았다.

itertools의 combinations를 이용해서 컬럼 인덱스를 조합한 배열을 만들어 탐색하면서 해당 조합에 해당하는 값들을 모은 다음 거기서 중복이 없다면, 해당 조합은 유일성을 만족하는 것이라고 생각했다. 

문제는 최소성이었는데, 문제에서 언급된 정의로 이해하자면 유일성을 만족하는 컬럼 집합 중에서 임의의 조합을 만들었을 때 거기서도  모든 튜플을 식별할 수 있어야하는 것이었다. 그래서 유일성을 만족하는 집합중에서 또 임의의 조합을 구한 뒤 그 조합으로 모든 튜플을 식별할 수 있는지 확인한 후 이를 만족하는 집합들의 갯수를 반환하는 것이라고 이해했다. (아니다)

최소성은 (학번, 이름)으로도 모든 튜플을 식별할 수 있지만 (학번)만으로도 모든 튜플을 식별할 수 있기에 최소성을 만족하지 않는다. 

그래서 유일성을 만족하는 원소 중에서 다른 유일성 원소를  포함하는 걸 모두 없애면 최소성을 만족하는 원소들을 구할 수 있다.

풀이 이해

• itertools의 combinations를 이용해서 컬럼을 조합한 배열을 만든다. (원소가 i개인 임의의 배열을 생성한다. 1 <= i <= 7) 
• 유일성 
  • 조합 원소들을 탐색하면서 해당하는 테이블 값들을 리스트를 만든 후 each result를 temp에 누적한다
  • 결과가 모두 식별되었다면 temp에는 총 n개(전체 튜플 갯수)만큼의 원소가 있을 것이다. 따라서 len(temp) == n이면 유일성을 만족하는 조합이므로 uniqueness에 추가한다 
• 최소성
  • 유일성을 만족하는 원소 중 다른 유일성 원소를 포함하고 있다면 이는 최소성을 만족하지 못한다. 
  • 원소를 포함한다는 것은 A intersection B == A 라는 의미이므로, 이를 set()과 intersection()을 이용한다
  • i번째 원소와 j번째 원소의 교집합이 i번째 원소라면 j 원소를 uniqueness에서 제거한다 
• uniqueness의 원소 갯수를 반환하면 후보키의 최대 갯수다 

- 정답 풀이 :

참고한 블로그

from itertools import combinations

def solution(relation):
    n, m = len(relation), len(relation[0])
    
    candidates = []
    for i in range(1, m + 1):
        candidates.extend(combinations(range(m), i))
    
    uniqueness = []
    for candi in candidates:
        temp = [tuple([item[i] for i in candi]) for item in relation]
        if len(set(temp)) == n:
            uniqueness.append(candi)
            
    answer = set(uniqueness)
    for i in range(len(uniqueness)):
        for j in range(i + 1, len(uniqueness)):
            if len(uniqueness[i]) == len(set(uniqueness[i]).intersection(set(uniqueness[j]))):
                answer.discard(uniqueness[j])
                
    return len(answer)

- 내가 작성한 유일성 코드 + 정답 최소성 코드 ㅋ

유일성 코드 구현할 때 막혔던 부분은 combinations로 만든 조합들을 어떻게 candidates에 추가할 것인가였다.

combinations의 결과를 list로 변경하면 [[0,2], [1,2], ,,,] 같은 형태가 되는데 이를 candidates에 바로 append를 하면 

candiates는 [ [[],[],[],,], [,,,,,], ,,,] 과 같이 삼중 리스트를 가지는데 이는 전개함에 있어 편한 스타일이 아니라 

조합 결과를 어떻게하면 이중 리스트로 만들 수 있을까 고민했다. 

그래서 생각해낸 게 append가 아닌 +를 하자는 것이었다. 리스트 + 리스트 는 단일 리스트이므로 내가 원하는 형태가 나온다고 생각했다. 

위 고민을 끝에 나온 코드는 다음과 같다 

    temp = [i for i in range(m)]
    candidates = []
    for i in range(1, m + 1):
        candidates += list(combinations(temp, i))

from itertools import combinations

def solution(relation):
    n, m = len(relation), len(relation[0])
    
    temp = [i for i in range(m)]
    candidates = []
    for i in range(1, m + 1):
        candidates += list(combinations(temp, i))
        
    # 유일성 만족하는 조합 구하기 
    uniqueness = []
    for candidate in candidates:
        unique = []
        for i in range(n):
            temp = []
            for j in range(len(candidate)):
                temp.append(relation[i][candidate[j]])
            
            if temp not in unique:
                unique.append(temp)   
                
        if len(unique) == n:
            uniqueness.append(candidate)
            
    # 최소성 만족하는 원소 구하기         
    answer = set(uniqueness)
    for i in range(len(uniqueness)):
        for j in range(i + 1, len(uniqueness)):
            if len(uniqueness[i]) == len(set(uniqueness[i]).intersection(set(uniqueness[j]))):
                answer.discard(uniqueness[j])
                
    return len(answer)