문제
https://school.programmers.co.kr/learn/courses/30/lessons/42890
풀이방법
유일성과 최소성을 만족하는 후보키를 선정하는 로직에 대해서 생각했다.
컬럼의 조합은 전체 컬럼을 (1 ~ 전체 컬럼의 개수) 만큼 고르는 경우의 수만큼 가능하다.
예시) 컬럼의 개수: N
컬럼의 조합의 개수: (N개에서 1개를 뽑는 경우) + (N개에서 2개를 뽑는 경우) + ... + (N개에서 N개를 뽑는 경우)
이때, 유일성을 만족하려면 set 자료형을 이용해서 겹치는 부분이 없는지 확인하면 되고
최소성을 만족하려면 이전에 유일성을 만족해서 후보키로 선정된 컬럼 조합이 포함된 경우에는 pass 하면 된다고 생각했다.
처음에는 전체 컬럼(1,2,3,4,...,N)에서 후보키로 선정된 컬럼의 번호를 빼는 방식으로 조합을 만들고 각 경우 유일성을 확인하는 방식으로 작성했다.
예시) 1개 뽑는 경우를 살펴본 결과, 컬럼 1이 후보키가 됨 => (2,3,4,...,N)에서 2개 뽑는 경우를 따져봄
2개 뽑는 경우를 살펴본 결과, 컬럼 (2,4)가 후보키가 됨 => (3,...,N)에서 3개 뽑는 경우를 따져봄
and so on...
그러나, 그렇게 짜니 몇 가지 케이스에서 오답이 나왔는데 그 이유는
전체 컬럼이 (0,1,2,3,4)이고, (1,2)컬럼이 후보키가 된 경우 1,2를 빼고 (0,3,4)에서 다시 조합을 구하게 되면 1,2 컬럼 중 하나만 포함되면서 유일성을 만족하여 후보키가 되는 경우(예를 들어 (2,3,4)가 유일성을 만족하는 경우)도 고려할 수 없게 되기 때문이다.
따라서, 이미 후보키라고 선정된 컬럼의 조합이 새롭게 살펴보는 컬럼의 조합의 부분집합인 경우에만 pass하는 방식으로 코드를 수정했더니 통과할 수 있었다.
부분집합인지 아닌지를 따질 때
set([1,2]) < set([1,2,3]) 이렇게 해서 True가 나오면 부분집합, False면 부분집합이 아닌 것으로 판별할 수 있다.
(파이썬은 대단해!!!)
코드
from itertools import combinations as comb
def isExist(index_list, key):
for k in key:
if set(k) < set(index_list):
return True
return False
def get_multiple_element(my_list, index):
return [my_list[i] for i in index]
def solution(relation):
n_col = len(relation[0])
org = list(range(n_col))
key = []
n = 1
while n <= n_col:
# print(org)
for index_list in list(comb(org, n)):
if isExist(index_list, key):
continue
else:
# print(index_list)
SET = set()
for row in relation:
SET.add(''.join(get_multiple_element(row, index_list)))
# print(SET)
if len(SET) == len(relation):
key.append(index_list)
# print("key:", key)
n += 1
return len(key)다른 사람의 풀이
from itertools import combinations
def solution(relation):
n_row = len(relation)
n_col = len(relation[0])
candidate = list()
for i in range(1, n_col+1):
candidate.extend(combinations(range(n_col), i)) #종목별로 만들 수 있는 모든 조합갯수 찾기
final = []
for keys in candidate:
tmp = [tuple([item[key] for key in keys]) for item in relation] # 주어진 키로 리스트의 index별 아이템 뽑아내기
if len(set(tmp)) == n_row: #set로 변경후 사라진게 없다면 key로 사용해도 무방
final.append(keys)
print(final)
answer = set(final[:])
print("answer", answer)
for i in range(len(final)):
for j in range(i+1, len(final)):
if len(final[i]) == len(set(final[i]).intersection(set(final[j]))): # key 중에 겹치는 부분이 있는 것을 삭제
answer.discard(final[j])
return(len(answer))
가능한 조합 모두 구하고
유일성 확인하고
최소성 만족하지 않는거 삭제하기
나의 경우, 최소성 만족하지 않는 경우 유일성을 따지지 않고 넘겼기 때문에 시간 효율은 나의 풀이가 좋을 것이라 생각된다.
