[프로그래머스] kakao 2018 코딩테스트 - 후보키 (python)

다른사람 풀이 참고해서 다시 코딩

from itertools import combinations

def solution(data):
    result = 0
    col_cnt=len(data[0])
    lst=list(range(0,col_cnt))
    c_lst=[]
    final=[]

    for i in range(1,col_cnt+1):
        c=combinations(lst,i)
        c_lst.extend(c)

    # 유일성 만족하는 조합 찾기
    for i in c_lst:
        final_tmp=[]
        for row in range(0,len(data)):
            tmp_lst=[]
            for t in i:
                tmp_lst.append(data[row][t])
            final_tmp.append(tuple(tmp_lst))
        #check (컬럼 조합한 값에서 중복이 없어야 유일성 만족)
        if len(set(final_tmp)) == len(data): 
            final.append(i)
            
    #최소성 만족하는 조합 골라내기
    final_set=set(final)
    for i in range(0,len(final)-1):
        for j in range(i+1,len(final)):
            # 최소성을 만족하지 못한 경우
            if set(final[i]) == set(final[i]) & set(final[j]):
                final_set.discard(final[j])

    result = len(final_set)

    return result

주의사항

• set의 요소값에는 mutable 객체 (list, set, dictionary)가 올 수 없습니다.
• 조합의 결과는 list.extend(c) 로 사용합니다.
• 2차원 배열의 컬럼길이는 len(arr[0]), row수는 len(arr) 로 구합니다. 

 

python 개념

1) 조합 (combinations)

from itertools import combinations

relation=[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]
n_col = len(relation[0])

###
candidates = []
for i in range(1, n_col + 1):
    combination_i = combinations(range(n_col), i)
    print(combination_i)
    candidates.extend(combination_i)
    print(candidates)
  
```
<itertools.combinations object at 0x7fb47e0e9100>
[(0,), (1,), (2,), (3,)]
<itertools.combinations object at 0x7fb47e0e9158>
[(0,), (1,), (2,), (3,), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
<itertools.combinations object at 0x7fb47e0e9100>
[(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)]
<itertools.combinations object at 0x7fb47e0e9158>
[(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 range(1, n_col + 1):
    for j in combinations(range(n_col), i):
        print(j)
       
```
(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)
```

 

조합 상세정리
https://it-sunny-333.tistory.com/25

 

2) 집합자료형 set

set의 원소에는 list, set, dictionary가 올 수 없습니다.

s=set([[1,2,3],3])
'''
Traceback (most recent call last):
  File "main.py", line 10, in <module>
    s=set([[1,2,3],3])
TypeError: unhashable type: 'list'
'''

s=set([{1,2,3},3])
'''
Traceback (most recent call last):
  File "main.py", line 10, in <module>
    s=set([{1,2,3},3])
TypeError: unhashable type: 'set'
'''

s=set([{1:"hi",2:"bye"},3])
'''
Traceback (most recent call last):
  File "main.py", line 10, in <module>
    s=set([{1:"hi",2:"bye"},3])
TypeError: unhashable type: 'dict'
'''

 

set 원소에 tuple은 올 수 있습니다.

s=set(((1,2,3),3))
print(s)
#set([(1,2,3),3])

s=set({(1,2,3),3})
print(s)
#set([(1,2,3),3])

s=set([(1,2,3),3])
print(s)
#set([(1,2,3),3])

 

set 추가설명
https://it-sunny-333.tistory.com/26

 

3) 2차원배열

relation=[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]
n_col = len(relation[0])

print(len(relation[0]))
# 4

print(len(relation))
# 6

• 컬럼수 구하기 : len(relation[0])
• row수 구하기 : len(relation)