프로그래머스 - 뉴스 클러스터링 (2018 KAKAO 블라인드 채용) / Level 2

문제 : https://programmers.co.kr/learn/courses/30/lessons/17677

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

풀이

def solution(str1, str2):
    strs = [list(str1.lower()), list(str2.lower())]

    for i in strs:  # 두 글자씩 끊어서 다중집합 만들기.
        for j in range(len(i) - 1):
            i[j] += i[j + 1]
        i.pop()

    for i in strs:  # 영문이 아닌 문자를 포함한 글자 쌍은 제외.
        for j in i[:]:
            for k in j:
                if ord(k) < 97 or ord(k) > 122:
                    i.remove(j)
                    break
    strs.sort(key=len)  # 길이가 작은 리스트를 바깥 루프로 돌릴 예정(시간 복잡도 고려).

    return int(jaccard(strs) * 65536)


def jaccard(str_arr):  # 자카드 유사도 측정.
    if str_arr[0] or str_arr[1]:
        u = str_arr[0] + str_arr[1]  # 전체 집합.
        intersection = []

        for i in str_arr[0]:
            for j in str_arr[1]:
                if i == j:  # 공통된 부분으로 교집합을 만들어줌.
                    intersection.append(i)
                    str_arr[1].remove(j)
                    break

        return len(intersection) / (len(u) - len(intersection))  # 교집합을 구하면 합집합은 원소 갯수로 파악가능.
    else:  # 둘 다 공집합일 경우.
        return 1

이 문제는 문자열을 다루는 문제이다.

내 생각이지만 카카오에서는 그나마 쉬운 문제로 문자열 다루는 문제를 자주 출제하는 듯하다.

자카드 유사도를 측정하는 함수와 측정할 수 있도록 전처리하는 함수로 나누었다.

 

자카드 유사도를 측정할 때 유의할 점은 중복도 허용하는 다중집합이기 때문에

단순히 set으로 변환한 뒤 교집합, 합집합을 구할 수 없다는 것이다.

이러한 일반적이지 않은 상황이 주어질수록 문제와 조건 안에 알고리즘이 묘사되기 때문에

문제와 조건을 유심히 읽어야 한다.