[프로그래머스] 👩‍💼 뉴스 클러스터링 - [1차] 2018 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT

반응형

 

KAKAO BLIND RECRUITMENT

👩‍💼 뉴스 클러스터링 문제 풀어보기

 

😃 나의 코드

import re
from collections import Counter as mset

p = re.compile("[a-z]{2}")

def multiSet(str):
    lst = []
    for idx in range(len(str)-1):
        if p.match(str[idx:idx+2]):
            lst.append(str[idx:idx+2])
    return lst

def solution(str1, str2):
    lst1 = multiSet(str1.lower())
    lst2 = multiSet(str2.lower())
    len_lst1 = len(lst1)
    len_lst2 = len(lst2)
    if len_lst1 == 0 and len_lst2 == 0:
        return 65536
    mset1 = mset(lst1)
    mset2 = mset(lst2)
    inter_lst = list((mset1 & mset2).elements())
    len_inter_lst = len(inter_lst)
    len_union_lst = len_lst1 + len_lst2 - len_inter_lst
    return int(len_inter_lst/len_union_lst *65536)

자카드 유사도라는 기법을 이용하여 두 집합의 유사도를 검사하는 문제입니다. 유사도를 검사할 때 각 문자열을 두 글자씩 끊어서 다중집합의 원소로 만든다.하고 영문자로 된 글자 쌍만 유효하다 했으니, 처음으로 해야할 건 두 글자씩 끊어서 다중 집합을 만들어야 합니다.

def multiSet(str):
    lst = []
    for idx in range(len(str)-1):
        if p.match(str[idx:idx+2]):
            lst.append(str[idx:idx+2])
    return lst

두 문자열에 같은 시행을 해야하기 때문에 multiSet이라는 함수를 새로 만들어서 진행했습니다. multiSet은 대소문자 차이는 무시한다라는 조건에 의해 모두 소문자로 바꿔서 다중집합을 만듭니다. 그 뒤 앞에서 부터 두 글자씩 끊어서 match를 이용해 미리 만들어놓은 정규 표현식과 비교합니다.

p = re.compile("[a-z]{2}")

정규 표현식은 알파벳 소문자 두 자리면 해당하는 match 객체를 반환하고 아니면 None을 반환하게 됩니다. 적절한 두 글자 문자열을 배열에 추가하여 반환합니다. 이 결과 값에서 두 배열 모두 크기가 0일 시 바로 65536을 반환해줍니다.

다음은 중복을 허용한 다중집합의 교집합을 구하는 과정입니다. 중복을 포함했기 때문에 set 자료형으로 진행할 시 중복이 사라져서 다른 해결책을 찾아야합니다. 저는 여기서 Python 내장 모듈인 collections의 Counter를 이용했습니다. Counter는 dict 자료형의 서브 클래스로 list를 Counter로 변환하게 되면 list의 요소를 key로 등장한 배열 내에서 등장한 횟수를 value로 하는 Counter 객체를 만들게 됩니다. Counter 객체는 set과 비슷하게 & 연산과 |연산이 가능합니다. &연산의 경우 Counter의 key별로 value의 최소값을 가진 Counter 객체를 반환하고, |연산의 경우 최대값을 가진 Counter 객체를 반환합니다.

mset1 = mset(lst1)
mset2 = mset(lst2)
inter_lst = list((mset1 & mset2).elements())

여기서 사용할 건 &연산입니다. multiSet으로 만들어진 두 다중 집합을 Counter 객체로 만든 뒤, 두 Counter 객체에 &연산을 하여 교집합의 Counter객체를 구합니다. 그 뒤 다시 list자료형으로 바꿉니다.

len_inter_lst = len(inter_lst)
len_union_lst = len_lst1 + len_lst2 - len_inter_lst
return int(len_inter_lst/len_union_lst *65536)

이제 모든 과정이 끝났습니다. 교집합에 해당하는 list의 길이를 측정하여 이를 교집합의 크기를 구합니다. 합집합의 크기는 두 집합의 크기를 더하고 교집합의 크기를 빼는 방식으로 구합니다. 이렇게하면 문제가 마무리 됩니다.

 

Written with StackEdit.

 

반응형

저작자표시

'Algorithm > Problem Solving' 카테고리의 다른 글

[프로그래머스] 👷‍♀️ 쇠막대기 / Python  (2)	2019.02.14
[프로그래머스] 🧱 프렌즈 4 블록 - [1차] 2018 카카오 블라인드 채용 / Python  (0)	2019.02.14
[프로그래머스] 👩‍💼 뉴스 클러스터링 - [1차] 2018 카카오 블라인드 채용 / Python / KAKAO BLIND RECRUITMENT  (0)	2019.02.14
[프로그래머스] 👨‍💻 캐시 - [1차] 2018 카카오 블라인드 채용 / Python  (0)	2019.02.13
[프로그래머스] 🎯 다트 게임 - [1차] 2018 카카오 블라인드 채용 / Python  (1)	2019.02.12
[프로그래머스] 🗺 비밀지도 - [1차] 2018 카카오 블라인드 채용 / Python  (0)	2019.02.12