새싹프로그래머의 이야기

문제: 두 개의 문자열이 있을 때, 자카드 유사도를 구하는 문제입니다.

조건:

• 입력된 문자열을 두 글자씩 끊어서 다중집합의 원소로 만듭니다.
• 이때, 토큰화 된 문자열에 특수문자가 들어갈 경우 제외합니다.
• 대문자와 소문자의 차이는 무시합니다.

풀이 코드:

num = 65536


def solution(str1, str2):
    answer = 0

    dic1 = dict()
    dic2 = dict()

    ls1 = len(str1)
    ls2 = len(str2)
    
    for i in range(ls1 - 1):
        key = str1.lower()[i:i + 2]
        if key.isalpha():  # 특수문자 있을 경우 제외.
            if dic1.get(key):
                dic1[key] += 1
            else:
                dic1[key] = 1

    for i in range(ls2 - 1):
        key = str2.lower()[i:i + 2]
        if key.isalpha():  # 특수문자 있을 경우 제외.
            if dic2.get(key):
                dic2[key] += 1
            else:
                dic2[key] = 1

    # intersection
    int_val = 0
    for i in dic1.keys():
        if i in dic2.keys():
            int_val += min(dic1[i], dic2[i])
    # Union 구하기
    uni_val = 0
    for i in dic1.keys():
        if i in dic2.keys():
            uni_val += max(dic1[i], dic2[i])
            dic2.pop(i)
        else:
            uni_val += dic1[i]

    for i in dic2.keys():
        uni_val += dic2[i]

    if uni_val == 0:
        answer = num
    else:
        answer = int(int_val / uni_val * num)

    return answer

풀이 설명:

for i in range(ls1 - 1):
    key = str1.lower()[i:i + 2]
    if key.isalpha():  # 특수문자 있을 경우 제외.
        if dic1.get(key):
            dic1[key] += 1
        else:
            dic1[key] = 1

자카드 유사도의 경우, 다중집합의 경우 같은 문자열도 다른 원소로 취급하므로 개 수를 세기 위해 딕셔너리를 활용하였습니다.

또한, 특수문자가 포함된 문자열을 제거하기 위해 .isalpha() 함수를 활용하였습니다.

str1 = '112' str2 = '1212' 일 경우,

dic1 = { '11' : 1 , '12': 1}

dic2 = {'12': 2 , '21:': 1} 가 됩니다.

# intersection
int_val = 0
for i in dic1.keys():
    if i in dic2.keys():
        int_val += min(dic1[i], dic2[i])

교집합을 구하는 부분은 다음과 같습니다. 토큰화된 문자열에 대한 개 수를 담은 딕셔너리의 key 값을 통해 같은 key가 존재할 경우, 

교집합이기 때문에 최소값을 더해주었습니다.

위의 예시에서 str1에는 '12'가 1개 , str2에는 '12'가 2개 있을 때 교집합은 1개 인 것을 보면 이해에 도움이 되실 것 입니다.

# Union 구하기
uni_val = 0
for i in dic1.keys():
    if i in dic2.keys():
        uni_val += max(dic1[i], dic2[i])
        dic2.pop(i)
    else:
        uni_val += dic1[i]

for i in dic2.keys():
    uni_val += dic2[i]

합집합의 경우, 두 문자열에 모두 존재하는 원소일 경우 개 수의 최대 값을, dic1에만 존재할 경우 그 원소의 개 수를 더하도록 하였으며, 

교집합에 해당되는 원소에 대한 값을 반영하였을 경우, pop() 함수를 통해 dic2에서 제거를 해주었습니다.

그리고 아직 dic2에만 있는 원소에 대한 값을 반영하지 않았으므로, 반복문을 별도로 구성해 값을 반영하여 주었습니다.

문제를 풀고 나서 다른 코드들을 보니 엄청 깔끔하고 파이써닉하게 풀어낸 코드가 있어서 소개드리고 마무리 하도록 하겠습니다.

num = 65536

def solution(str1, str2):
    answer = 0

    token1 = [str1[i:i + 2].lower() for i in range(len(str1) - 1) if str1[i:i + 2].isalpha()]
    token2 = [str2[i:i + 2].lower() for i in range(len(str2) - 1) if str2[i:i + 2].isalpha()]

    intersect = set(token1) & set(token2)
    uni = set(token1) | set(token2)


    uni_val = sum(max(token1.count(i), token2.count(i)) for i in uni)
    intersect_val = sum(min(token1.count(i), token2.count(i)) for i in intersect)


    if uni_val == 0:
        answer = num
    else:
        answer = int(intersect_val/uni_val*num)
    return answer

다중집합의 원소의 개 수로 답을 구하는 문제이므로, set()과 count() 함수를 통해 깔끔하게 풀어낸 풀이가 있더라구요. 보면서 감탄만 나왔던 코드였습니다. 제가 앞으로 파이썬으로 알고리즘을 공부해가면서 나아가야할 방향을 보여주는 듯 했습니다.