[python]programmers-뉴스클러스터링(자카드 유사도)

2018 KAKAO BLIND RECRUITMENT

문제 : 뉴스 클러스터링

입력되는 두개의 문자열의 자카드 유사도를 계산하는 문제이다.

• 입력되는 문자열을 두글자씩 끊어야 한다(HELLO -> HE, EL, LL, LO)
• 예를들어 입력된 문자열을 두글자씩 끊었을 때 str1 = {aa, aa, ab, bb, bc}, str2 = {aa, aa, ab, ab, bb}라고 해보자. 
• str1 | str2 (합집합) = {aa, aa, ab, ab, bb, bc}
• str1 & str2 (교집합) = {aa, aa, ab, bb}
• 일반 집합의 합/교집합 결과와 다르게, 만약 aa가 두 문자열에 두번 나타나면 aa 두개가 합집합, 교집합에 들어간다.
• 만약 str1에는 ab가 2개, str2에는 ab가 하나라면, 교집합에는 ab 한개(개수가 작은것), 합집합에는 ab가 두개(개수 중 큰것) 가 들어간다.

내 코드

def makeSet(s) :
    tmp_list = []
    for i in range(len(s) - 1) :
        tmp = s[i:i+2]
        if(tmp.isalpha()) :
            tmp_list.append(tmp)
    return tmp_list

def solution(str1, str2):
    str1_list = makeSet(str1.lower())
    str2_list = makeSet(str2.lower())

    str1_set = set(str1_list)
    str2_set = set(str2_list)
    union = list(str1_set | str2_set)
    inter = list(str1_set & str2_set)

    union_score = 0 # 합집합(max)
    inter_score = 0 # 교집합(min)

    for i in union :
        union_score += max(str1_list.count(i), str2_list.count(i))

    for i in inter :
        inter_score += min(str1_list.count(i), str2_list.count(i))

    if(union_score == 0) :
        return 65536

    similarity = inter_score / union_score
    return int(similarity * 65536)

 

makeSet은 문자열을 두글자 씩 끊은 list를 반환하는 함수이다. 원래의 문자열을 슬라이싱하여 슬라이싱 된 결과가 오로지 문자인지 확인했다.(특수문자나 공백, 숫자가 들어가 있으면 제거해야한다)

오로지 알파벳으로 되어있는지 확인하기 위해 슬라이싱한 결과가 isalpha인지 확인해주었다.

 

두글자씩 끊은 문자열이 들어있는 list(str1_list, str2_list)를 집합(str1_set, str2_set)으로 바꿔주었다(중복제거)

그리고 두 집합의 교집합(str1_set & str2_set)과 합집합(str1_set | str2_set)을 구해주었다.(어차피 결과적으로 inter/union에 있는 원소들인데, 그것이 몇개가 존재하느냐 만 알면 되기 때문이다)

 

for문을 돌려주기 위해 합/교집합을 list로 만들어주었다(union/inter)

 

위의 예제처럼 union이 {aa, ab, bb, bc} 라고 생각해보자.

• str1_list에 aa는 2개가 있고, str2_list에 aa는 2개가 있다.
• 그러므로 aa의 결과로 합집합 원소의 갯수는 2개 이다.
• str1_list에 ab는 1개, str2_list에서 ab는 2개가 있다.
• 합집합 이므로 개수가 많은 것을 선택한다.({ab} | {ab, ab} = {ab, ab}이므로 max를 사용한다)
• 따라서 ab의 갯수는 2이므로 합집합 원소의 갯수는 4가 된다.
• 이런 알고리즘으로 계속 검사한다.

교집합은 반대로 {ab} & {ab, ab} = {ab} 이므로 min을 찾아준다.

 

마지막으로 교집합갯수(inter_score) / 합집합갯수(union_score)를 계산해주어야 하는데, union_score가 0일때는 error가 나므로 union == 0일 때 경우를 생각해준다.

 

union == 0 이 true인 경우는 두 문자열을 두개씩 쪼갰을 때의 결과가 빈 리스트라는 것이다

E=M*C^2 , e=m*c^2 두가지가 들어왔다고 생각해보자. 각 문자열을 두개씩 나누었을 때 특수문자가 항상 포함되므로 결국에는 빈 리스트가 된다. 이때는 유사도를 1로 보고 1 * 65536 을 반환해주면된다. 

(여기서 드는 의문은 a=b*c^5와 z-w-x-7 두개가 들어와도 유사도가 1이 되는데, 이 두개가 유사하다 볼수있는가..?)

 

유사도는 0 ~ 1사이의 수 이므로 유사도*65536 의 결과에 정수값만 출력하라 했으니 int로 씌워 정수값만 반환해준다.