문제:
풀이방법:
컬럼의 길이가 최대 8이므로 가능한 모든 경우의 조합을 다 따져보아도 문제가 없을 것이라고 생각했다.(최대 2^8=256개이기 때문이다.) 따라서 우선 check 함수를 통해서 유일성을 만족하는지 파악을 했다.
유일성을 만족하는 조합을 기준으로 서로 비교하면서 최소성을 만족하는지 확인하였다. 이들을 집합이라고 생각한다면 (1)은 (1,2)의 부분집합이 되게 된다. 따라서 set에서 부분집합인지 확인해주는 내장함수는 issubset을 사용해서 부분집합인지 확인하였다. 그리고 해당하는 조합이 있다면 remove를 통해서 제거해줬다.
그리고 남은 answer의 길이를 구함으로써 후보키의 갯수를 얻을 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
def check(columns,tuples,relation):
sets=set()
for rel in relation:
tup=''
for col in columns:
tup+=rel[col]
sets.add(tup)
if len(sets)==tuples:
return True
else:
return False
def solution(relation):
answer=[]
import itertools
columns=list(range(len(relation[0])))
tuples=len(relation)
for i in range(1,len(columns)+1):
candidate=list(itertools.combinations(columns,i))
for candi in candidate:
if check(list(candi),tuples,relation):
answer.append(list(candi))
for i in answer[:]:
for j in answer[:]:
if i==j:
continue
if set(i).issubset(set(j)):
answer.remove(j)
return len(answer)
|
cs |
문제링크:
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1890. 점프 (0) | 2019.10.04 |
|---|---|
| [Programmers]2017 Kakao.다트 게임 (0) | 2019.10.02 |
| [Programmers]2018 Kakao.실패율 (0) | 2019.09.30 |
| [Programmers]2018 Kakao. 오픈채팅방 (0) | 2019.09.29 |
| [Programmers]2017 Kakao.비밀지도 (0) | 2019.09.28 |
