[프로그래머스 Level2] 후보키 - 파이썬(Python) - 2019 KAKAO BLIND RECRUITMENT

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

프로그래머스

문제 설명

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다.
그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.
물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.
따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.

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

 

 

---

코드만 보면 많이 복잡하다... 그래도 의외로(?) 한 시간 안에 풀린 문제였다.

 

< 풀이 과정 >

1, 2번째 for문: 문제 예제에서, 한 컬럼(column)의 길이가 4이므로 정답이 될 후보키들은 1개, 2개, 3개, 4개짜리가 될 수 있으며, 그러한 후보키들의 인덱스들을 조합하는 combinations(idxList, cnt) 중에 인덱스 값이 있다.

combinations(idxList, cnt)=(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)

 

3번째 for문 (relation을 순회): 후보키가 될 수도 있는 인덱스의 배열(idxs)이 정해진 상태이다. 순회를 돌며 인덱스대로 정보들을 모으고, 서로 겹치진 않는지, 후보키가 될 수는 있을지 확인한다.

ex. idx=(1,2) 의 경우,

 lines = [['ryan', 'music'], ['apeach', 'math'], ['tube', 'computer'], ['con', 'computer'], ['muzi', 'music'], ['apeach', 'music']]

=> 후보키가 될 수 있는 경우이다..!

 

4번째 for문 (hoboKeys를 순회): 모든 튜플들은 꼭 필요한 속성끼리만 존재해야 한다.

예로 들어, 문제에선 인덱스 (0)이 후보키가 가능하다고 밝혔다. 이때, 인덱스 (0, 1), (0, 3), (0, 1, 2, 3)이 인덱스 (0)으로 인해 구별되어 후보키가 되는 경우는 없어야 한다. (최소성 보장)

 

=> 후보키가 될 수 있다면 hoboKeys에 후보키를 넣고 계속한다.

 

 

 

<< 전체 코드 >>

from itertools import combinations

def solution(relation):
    answer = 0
    hoboKeys = []
    idxList = [i for i in range(len(relation[0]))]
    for cnt in range(1, len(relation[0])+1):
        for idxs in combinations(idxList, cnt):
            # 인덱스들에 따라 후보키로 구성된 중복없는 line들을 구한다.
            possible = True
            lines = []
            for line in relation:
                li = []
                for idx in idxs:
                    li.append(line[idx])
                if li in lines:
                    possible=False
                    break
                lines.append(li)
            # 최소성을 지켜야 한다.
            # 기존 후보키를 통해 현재 idxs가 꼭 필요한 속성들로만 구성된건지 확인한다.
            for v in hoboKeys:
                cnt = len(v)
                for n in v:
                    if n in idxs:
                        cnt -= 1
                if cnt == 0:
                    possible = False
                    break
            # 새로운 후보키가 될 수 있는지 확인한다. 
            if possible:
                hoboKeys.append(list(idxs))
                answer += 1
    return answer