파이썬 알고리즘 246번 | [프로그래머스 뉴스 클러스터링]

246. 뉴스 클러스터링

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

def solution(str1, str2):

    str1 = list(str1.lower())
    str2 = list(str2.lower())

    refin1 = []
    refin2 = []
    
    for i1 in range(len(str1)-1) : 
        if str1[i1].isalpha() and str1[i1+1].isalpha() : 
            refin1.append((str1[i1:i1+2]))
    
    for i2 in range(len(str2)-1) : 
        if str2[i2].isalpha() and str2[i2+1].isalpha() : 
            refin2.append((str2[i2:i2+2]))

    # refin1.sort(); refin2.sort()

    # print("refin 1 : " ,refin1)
    # print("refin 2 : " ,refin2)

    # 교집합
    if len(refin1) > len(refin2) :
        longer = refin1.copy()
        shorter = refin2.copy()

    else : 
        longer = refin2.copy()
        shorter = refin1.copy()

    # 교집합 
    inter = []
    for in1 in longer: 
        if in1 in shorter : 
            inter.append(in1)
            shorter.remove(in1)
            
    # 합집합 
    all = refin1+refin2

    cmp = inter.copy()
    for al in all : 
        if al in cmp : 
            all.remove(al)
            cmp.remove(al)

    # print('INTER : ', inter )
    # print('ALL : ', all )
    
    if len(all) !=0 : 
        answer = (len(inter)/len(all)) * 65536
    else : 
        answer = 65536
    return int(answer)

<다른 분의 풀이 or 내 틀렸던 풀이, 문제점>

난관1

    refin1set = set(refin1)
TypeError: unhashable type: 'list'

• 이런 에러 난다고 나타남
• why ?
  리스트를 set으로 바꾸는 거 ㄱㅊ은데

원인 :

파이썬에서 List는 변동가능하기때문에, 만들어지지 않는 것인데요. 즉, List를 Tuple로 만들어줘야 set이 문제 없이 만들어진다.
출처: https://sundries-in-myidea.tistory.com/76 [얇고 넓은 개발 블로그:티스토리]

Sets require their items to be hashable. Out of types predefined by Python only the immutable ones, such as strings, numbers, and tuples, are hashable. Mutable types, such as lists and dicts, are not hashable because a change of their contents would change the hash and break the lookup code.

내가 set 로 바꾸려던 아이의 속모습

https://stackoverflow.com/questions/13464152/typeerror-unhashable-type-list-when-using-built-in-set-function

해결책 :

Since the lists are mutable, they cannot be hashed. The best bet is to convert them to a tuple and form a set, like this

>>> mat = [[1,2,3],[4,5,6],[1,2,3],[7,8,9],[4,5,6]]
>>> set(tuple(row) for row in mat) # 이렇게 바꿔주면 되지
set([(4, 5, 6), (7, 8, 9), (1, 2, 3)])

난관2

걍 쉽게 생각해서 다 set 으로 바꿔버리고 합집합 교집합 연산만 진행해주면 알았는데, 파이썬 set은 중복제거해주는 역할을 하거등?? 근데 여기서는 중복제거하면 안된다 ㅠㅠ 흑흑

def solution(str1, str2):

    str1 = list(str1.lower())
    str2 = list(str2.lower())

    refin1 = []
    refin2 = []
    
    for i1 in range(len(str1)-1) : 
        if str1[i1].isalpha() and str1[i1+1].isalpha() : 
            refin1.append((str1[i1:i1+2]))
    
    for i2 in range(len(str2)-1) : 
        if str2[i2].isalpha() and str2[i2+1].isalpha() : 
            refin2.append((str2[i2:i2+2]))

    # refin1set = set(tuple(r1) for r1 in  refin1)
    # refin2set = set(tuple(r2) for r2 in  refin2)

    # 교집합
    if len(refin1) > len(refin2) :
        longer = refin1
        shorter = refin2

    else : 
        longer = refin2
        shorter = refin1

    # 교집합 
    inter = []
    for in1 in shorter.copy() : 
        if in1 in longer : 
            inter.append(in1)
            shorter.remove(in1)
            longer.remove(in1)

    # 합집합 
    tmp_all = refin1+refin2
    all = [item for item in tmp_all if not in inter]

    
    if len(all) !=0 : 
        answer = (len(inter)/len(all)) * 65536
    else : 
        answer = 65536
    return int(answer)

print(solution("FRANCE", "french"))
print(solution("handshake", "shake hands"))
print(solution("aa1+aa2", "	AAAA12"))
print(solution("E=M*C^2", "e=m*c^2"))

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장
A = {1, 1, 2, 2, 3},
다중집합
B = {1, 2, 2, 4, 5}라고 하면,
교집합 A ∩ B = {1, 2, 2},
합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로,
자카드 유사도 J(A, B) = 3/7,
약 0.42가 된다.

<반성 점>

• 또 문제 제대로 안읽고 나대다가 시간 더 오래걸림!

<배운 점>

• 다중집합 이란 것이 있으면 내가 커스터마이징해서 만들어줘야하지

자주 유용하게 쓰일 처리문

[item for item in longer if item in shorter]