[PROGRAMMERS] 2018 KAKAO BLIND RECRUITMENT : 뉴스클러스터링 Python

이 문제는 문제 자체가 어렵다기보다는 손 코딩을 통해 어떻게 풀어나갈지 정하고 풀기 시작하지 않는다면, 문제를 풀면서 코드가 복잡해지는 문제 같았다. 나도 손 코딩부터 하지 않고 하여 코드가 뒤죽박죽이 됐었다.

이 문제는 설명이 매우 길지만 요약하자면 주어진 두개의 문자열을 각각 문자로만 이루어진 두 개의 단어로 쪼개어 다중집합으로 저장한 후, 자카드 유사도를 구하는 문제이다. 

문제를 읽으면서 다중집합과 자카드유사도를 보며 처음 보는 개념에 당황했지만,  개념을 이해하기보다는 문제가 시키는 대로 풀려고 노력했다. 다중집합은 중복을 허용하는 집합이었고 그렇기 때문에 교집합과 합집합을 구하는 방식이 일반 집합과 달랐다.

나는 문제를 풀기위해 총 세 가지 부분으로 나누어 풀었다.
Q1. 문자열을 두글자씩 모두 알파벳인 문자로 나누어 대문자 형태로 리스트에 저장한다
A1. 두글자씩 슬라이 싱하여 re.match과 None이 아닌 값을 저장하자 

요즘 re라이브러리를 공부하다보니 re라이브러리를 사용하는 것이 먼저 떠올랐었는데,  isalpha를 이용하는 것이 더 좋아 보였다.

Q2. 자카드 유사도를 구하기 위하여 교집합과 합집합을 구한다
A2. 합집합의는 공통 원소의 최대갯수와 나머지 공통원소가 아닌 원소들, 교집합에는 공통원소의 최소 개수

이 부분에서 set을 이용해서 푸신분들이 많아 보였지만, 나는 문제를 풀 때 그 생각이 나지 않을뿐더러 코드를 봐도 이해가 되지 않았다. 정말 똑똑한 사람들이 많은 것 같다.

Q3. 마지막으로 합집합과 교집합의 원소 개수를 이용해 자카드 유사도를 구한다.
A3. 이 부분은 예외처리만 해준다면 쉽게 구할 수 있었다.

전체 코드를 보자면

import re

def solution(str1, str2):
    exp = re.compile('[a-zA-Z][a-zA-Z]')
    strA = [str1[i:i+2].upper() for i in range(len(str1)-1) if exp.match(str1[i:i+2])]
    strB = [str2[i:i+2].upper() for i in range(len(str2)-1) if exp.match(str2[i:i+2])]

    union = []
    inter = []
    stand = list(set(strA+strB))
    for st in stand:
        if st in strA and st in strB:
            union.extend([st]*max(strA.count(st), strB.count(st)))
            inter.extend([st]*min(strA.count(st), strB.count(st)))

    for st in strA + strB:
        if st not in inter:
            union.append(st)

    if len(union) == 0:
        return 65536
    return int((len(inter)/len(union) * 65536) // 1)

solution('FRANCE', 'french')

이렇게 된다.

오늘 다시 한번 더 손 코딩의 중요성을 느꼈다. 어렵지 않은 문제인데 문제를 풀면서 코드가 복잡해지니 더 헷갈렸던 것 같다.

하루한개 알고리즘 파이륑!