프로그래머스 [1차] 뉴스 클러스터링(Python)

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

프로그래머스

  이번 문제는 무려 2018 KAKAO BLIND RECRUITMENT 문제! 물론 저도 푼 것을 보면 문제들 중 가장 난이도가 쉬웠던 문제가 아니었을까 싶습니다. 이번 문제는 두 문자열의 자카드 유사도를 계산하는 문제였습니다.

저의 풀이

  자카드 유사도를 구할 때 핵심은 교집합이었습니다. 이번 문제에서 사용되는 집합은 다중 집합(원소가 중복될 수 있는 집합)이었기 중복 원소들 간의 교집합 계산을 생각해야 했습니다. 그래서 저는 파이썬에서 제공하는 Counter를 사용해 각 집합 별로 원소의 개수를 세고 두 집합 중 원소의 개수가 적은 수만큼 교집합에 추가하는 방법으로 진행했습니다. Counter에 대한 사용 방법은 아래 사이트를 보시면 됩니다. 그리고 제가 적은 코드는 아래와 같습니다.

collections — Container datatypes — Python 3.8.13 문서

from collections import Counter


def get_intersection(set1, set2):
    counter1, counter2 = Counter(set1).most_common(), Counter(set2).most_common()
    base, check = (counter2.copy(), counter1.copy()) if len(counter1) > len(counter2) else (counter1.copy(), counter2.copy())
    intersection = []
    for i in range(len(check)):
        item, cnt = check[i]
        for j in range(len(base)):
            if base[j][0] == item:
                intersection.extend([item] * min(cnt, base[j][1]))
                break
    return intersection


def solution(str1, str2):
    str1, str2 = str1.lower(), str2.lower()
    if len(str1) == 2 and len(str2) == 2:
        return 65536 if str1 == str2 else 0

    multiset_1 = [str1[i:i+2] for i in range(len(str1) - 1) if str1[i:i+2].isalpha()]
    multiset_2 = [str2[i:i+2] for i in range(len(str2) - 1) if str2[i:i+2].isalpha()]
    if len(multiset_1) == 0 and len(multiset_2) == 0:
        return 65536
    else:
        intersection = get_intersection(multiset_1, multiset_2)
        return int(len(intersection) / ((len(multiset_1)) + len(multiset_2) - len(intersection)) * 65536)

  프로그래머스 채점 결과, 최대 1.32ms, 10.5MB 소모했습니다. 아마 교집합을 만드는데 이중 for문을 사용한 것이 속도가 느린 원인이 아닐까 생각합니다.

다른 사람의 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/17677/solution_groups?language=python3 

프로그래머스

  다른 사람들의 풀이를 보면서 Counter 사용 방법 중 하나를 배웠습니다. Counter instance끼리 집합 연산이 가능합니다! 덕분에 교집합을 만드는 코드가 많이 짧아지고 보기 간결해졌습니다. 이를 적용한 코드는 아래와 같습니다.

from collections import Counter

def get_intersection(set1, set2):
    counter1, counter2 = Counter(set1), Counter(set2)
    return counter1 & counter2

def solution(str1, str2):
    str1, str2 = str1.lower(), str2.lower()
    if len(str1) == 2 and len(str2) == 2:
        return 65536 if str1 == str2 else 0

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

    if len(multiset_1) == 0 and len(multiset_2) == 0:
        return 65536
    else:
        intersection_len = sum(get_intersection(multiset_1, multiset_2).values())
        return int(float(intersection_len) / ((len(multiset_1)) + len(multiset_2) - intersection_len) * 65536)

프로그래머스 채점 결과, 최대 0.23ms, 10.5MB 소모했습니다.