[프로그래머스] 후보키

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

프로그래머스

SQL에서 후보키가 무엇인지 찾는 문제이다.

문제 풀이 과정은 다음과 같다

1. combinations 라이브러리를 사용하여 구할 수 있는 모든 key의 종류를 구한다.

2. 우선 유일성을 만족하는 것을 찾기 위해 해당 key를 바탕으로 중복 유무를 판단한다.

3. 유일성을 만족한 key에서 최소성을 만족하는 것을 찾기 위해 각각의 교집합의 유무를 판단한다.

from itertools import combinations

def solution(relation):
    answer = []
    keys = [i for i in range(len(relation[0]))]
    combis = []
    
    # 1번
    for i in range(1, len(relation[0])+1):
        for j in combinations(keys, i):
            combis.append(j)
    
    # 2번과 3번
    for combi in combis:
        check = []
        for i in range(len(relation)):
            c = ""
            for j in combi:
                c += relation[i][j]
            check.append(c)
            
        # 2번
        if len(list(set(check))) == len(relation):
            flag = True
            
            # 3번
            for a in answer:
                if set(a).issubset(set(combi)):
                    flag = False
                    break
            
            if flag:
                answer.append(combi)
            
    return len(answer)

 

배운 점 및 오답 코드

이번 시간을 통해 새로 배운 점은 issubset 메서드이다.

이름에서도 알 수 있듯이 set 자료구조에서만 사용 가능하다.

필자의 경우, 최소성을 판별하는 과정에서 issubset을 사용하기 전에 각각을 순회하면서 비교하는 방법을 사용하였다.

하지만 해당 방법으로는 계속 정확성이 46.4점이 나와서 다른 방법을 모색하던 도중, issubset 메서드를 알게 되었다.

그렇다면 원리는 같아 보이는데, 왜 정답은 아닌 것일까?

 

사실 정답 코드와 오답 코드의 최소성 식별 과정은 조금 다르다.

 

* 정답 코드 : 

set(a).issubset(set(b))

정답 코드의 경우에는 a가 b에 완전 포함되어 있으면, True를 반환한다.

예를 들자면, a : {1, 2, 3}, b : {1, 2, 3, 4}와 같이 a가 b의 부분 집합일 때이다.

 

* 오답 코드 : 

set(a).intersection(set(b))

오답 코드의 경우에는 아래의 원본 코드에서도 보면 알 수 있지만, 해당 코드는 insersection을 의미한다. (intersection의 메서드의 존재를 몰라서 직접 구현한 것이다.)

두 집합 간의 합집합이 존재하면 True를 반환한다.

코드에서 combinations를 통해 발견한 모든 경우의 수를 하나하나 검토하기 때문에 배열의 길이가 작은 경우의 key먼저 검토하기에 필자는 해당 방법도 문제가 없다고 생각했었다.

하지만 이 생각이 오답 결과를 불러왔다.

 

{ {"a","1","aaa","c","ng"},
{"a","1","bbb","e","g"},
{"c","1","aaa","d","ng"},
{"d","2","bbb","d","ng"}}

다음과 같은 예시가 있다고 하자

유일성을 검사를 하면 02, 03, 04, 13, 23, 012, 013, 014, 023, 024, 034, 123, 134, 234, 0123, 0124, 0134, 0234, 1234, 01234와 같은 key들이 살아남을 것이다.

하지만 02와 03을 보도록 하자.이 둘은 최소성을 모두 갖췄음에도 불구하고 intersection을 사용하면 합집합이 존재하기 때문에 후보키가 아니라고 판단한다.즉, 합집합을 사용하여 최소성을 판단하는 것 자체가 잘못된 방식인 것이다.

항상 여러 방식을 생각하고 반례를 빠르게 찾는 것이 매우 중요함을 느낄 수 있었다. (물론 이게 매우 어렵지만 ..)

from itertools import combinations

def solution(relation):
    answer = 0
    visited = []
    dd = []
    com = [i for i in range(len(relation[0]))]
    
    for i in range(1, len(relation)+1):
        for combis in combinations(com, i):
            flag = True
            temp = []
            d = []
            for j in range(len(relation)):
                c = ""
                for combi in combis:
                    c += relation[j][combi]
                    d.append(combi)
                if c not in temp:
                    temp.append(c)
                else:
                    flag = False
                    break
            if not flag:
                continue
            
            d = list(set(d))
            flag2 = True
            for i in d:
                if i in visited:
                    flag = False
                    break
            if flag:
                dd.append(d)
                for i in d:
                    visited.append(i)
                
    return len(dd)