[프로그래머스(파이썬/Python)] 후보키(2019 카카오 블라인드)

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

코딩테스트 연습 - 후보키

 

카카오 기출 문제는 꼭 한 번씩 2~3개의 테스트케이스가 틀리는 경우가 많은 것 같습니다. 맞왜틀도 실력이라고 생각하기 때문에 아직 갈 길이 먼 것 같습니다...

 

이 문제는 주어지는 컬럼의 수가 1이상 8이하이고, 릴레이션의 개수도 20이하이기 때문에 완전탐색을 해야겠다고 생각했습니다. 즉, 모든 가능한 후보키 조합 중에서 유일성과 최소성을 만족하는 후보키를 세면 되겠다고 생각했죠.

 

따라서, combinations 라이브러리를 이용하여 모든 가능한 후보키 조합을 찾아냈고 각 후보키 조합에 대해 우선적으로 유일성을 갖는지 확인했습니다. 유일성 체크하는 방법은 "모든 릴레이션을 순회하면서 후보키에 해당하는 컬럼의 값들을 리스트에 넣고, 리스트에 중복이 생기면 후보키가 아니다"는 로직을 이용했습니다.

 

다음으로 어떤 후보키가 유일성을 만족하면 이전에 이미 구했놓았던 후보키가 이 후보키의 부분집합이 되면 최소성이 깨진다는 논리로 접근했습니다.

 

아래 코드를 보면 아시겠지만, combinations를 통해 후보키를 구할 때 갯수가 1인 것부터 늘려나가기 때문에 기존에 존재하는 후보키가 현재 후보키의 부분집합이 되는가?를 기준으로 삼을 수 있었습니다.

 

하지만 처음에 몇 개의 테스트 케이스를 틀렸는데, A 후보키가 B 후보키의 부분집합임을 체크할 때 A in B처럼 풀게 된다면 A의 각 컬럼이 B에 모두 존재한다고 하더라도, 연속된 경우가 아니라면 체크가 되지 않기 때문에 오답을 낼 수 있습니다. 이 부분을 조심해야 합니다!

 

따라서 저는 이 문제를 해결하기 위해 단순하게 각 후보키의 컬럼들을 하나하나 비교하면서 이중 for-loop를 도는 방식으로 해결했습니다.

 

[풀이]

from itertools import combinations as C

def solution(relation):
    # column의 개수 c <= 8, row의 개수 r <= 20 -> 완전탐색
    r, c = len(relation), len(relation[0])
    columnIndex = [i for i in range(c)]
    candidateKey = []

    # 가능한 모든 키 조합에 대해
    for i in range(1, c+1):
        for keyComb in list(C(columnIndex, i)):
            uniqueness = True
            chk = []

            # 릴레이션에서 해당 키의 튜플만 저장
            for rel in relation:
                temp = []
                for key in keyComb:
                    temp.append(rel[key])

                # 유일성 체크
                if temp in chk:
                    uniqueness = False
                    break
                else:
                    chk.append(temp)

            # 유일성 테스트를 통과한다면
            if uniqueness:
                # 최소성 체크
                currKey = ''.join(map(str,keyComb))
                minimality = True

                # 이전에 결정된 후보키를 모두 포함하는 키가 있다면 최소성 만족 X
                for existingKey in candidateKey:
                    count = len(existingKey)
                    for ek in existingKey:
                        for ck in currKey:
                            if ek == ck:
                                count -= 1
                    if count == 0:
                        minimality = False
                        break

                if minimality:
                    candidateKey.append(currKey)
    return len(candidateKey)