728x90
반응형
문제 출처:https://school.programmers.co.kr/learn/courses/30/lessons/42890
풀이:
첫 시도:
from itertools import combinations
def solution(relation):
row = len(relation) # 행
col = len(relation[0]) # 열
#가능한 속성의 모든 인덱스 조합
combi = []
for i in range(1, col+1):
combi.extend(combinations(range(col), i))
arr = set()
for i in combi:
tmp = [tuple([item[key] for key in i]) for item in relation]
if row == len(set(tmp)): # 겹치는게 없으니 열이 같다 >> 중복된 값이 없음 # 유일성
arr.add(i)
res = set()
idxx = 0
idx =set({idxx})
while idxx != col+1:
flag =True
for i in arr:
if idx.issubset(set(arr)):
flag = False
break
if flag:res.add(i)
idxx += 1
return len(res)
from itertools import combinations
def solution(relation):
row = len(relation) # 행
col = len(relation[0]) # 열
#가능한 속성의 모든 인덱스 조합
combi = []
for i in range(1, col+1):
combi.extend(combinations(range(col), i))
arr = set()
res = []
for i in combi:
tmp = [tuple([item[key] for key in i]) for item in relation]
if row == len(set(tmp)): # 겹치는게 없으니 열이 같다 >> 중복된 값이 없음 # 유일성
arr.add(i)
# 유일성 통과하면 희소성
flag = True
for j in res:
if set(j).issubset(set(i)): # 겹치는게 있으면
flag = False
if flag: # 맨 처음 빈 리스트일때 넣음 / 희소성일때 넣음
res.append(i)
return len(res)
#가능한 속성의 모든 인덱스 조합
combi = []
for i in range(1, col+1):
combi.extend(combinations(range(col), i))
# >>[(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)]
이런식으로 조합이 나옴
for i in combi:
tmp = [tuple([item[key] for key in i]) for item in relation]
그럼 0 / 1 / .. / 0,1,2,3 / 조합을 써서
tmp라는걸 만든다.
if row == len(set(tmp)): # 겹치는게 없으니 열이 같다 >> 중복된 값이 없음 # 유일성
arr.add(i)
유일성 테스트
flag = True
for j in res:
if set(j).issubset(set(i)): # 겹치는게 있으면
flag = False
if flag: # 맨 처음 빈 리스트일때 넣음 / 희소성일때 넣음
res.append(i)
유일성 테스트 통과하면 희소성 테스트
반응형
댓글