🎁 문제 링크

[1]차 뉴스 클러스터링

🎁 문제 풀이

접근 순서

1. 문자열을 2개씩 자른 집합을 만든다.
2. 합집합과 교집합을 구한다.
3. 원소를 중복으로 허용하는 다중 집합이 있으므로 고려해 준다.
4. 주어진 조건대로 답을 구해준다.

1. 문자열을 2개씩 자른 집합을 만든다.

• 2개의 집합을 만드는 작업이 반복되므로 함수를 이용하여 호출해주기로 하였다.

def cut(ss, set_s):
    for i in range(len(ss)-1):
    # 알파벳이 아닌경우는 무시
        if ss[i:i+2].isalpha():
        # 대소문자 구별이 없으므로 모두 소문자로 만들어준다.
            set_s.append(ss[i:i+2].lower())
    return set_s

cut 이라는 함수를 만들어 문자열을 2개씩 자른 리스트를 반환한다.

2. 합집합과 교집합을 구한다.

    set_a, set_b = [], []
    cut(str1, set_a)
    cut(str2, set_b)
    # 합집합
    union = set(set_a) | set(set_b)
    # 교집합
    intersection = set(set_a) & set(set_b)
    

3. 원소를 중복으로 허용하는 다중집합이 있으므로 고려해 준다.

이부분이 이문제를 푸는데 있어서 가장 걸림돌이 됐었던 부분이다.
이 작업을 하지 않은채 문제를 풀게 되면 3번째 테스트 케이스인 str1 = aa1+aa2, str2 = AAAA12 에서 오류가 발생하게 된다. 중복을 허용하지 않았을 경우 set_a = {aa, aa}, set_b = {aa, aa, aa} 가 되는데 union = {aa}, intersection = {aa} 가 되기 때문에 답을 구하는데 있어서 오류가 발생한다.
따라서, 문제에 나와있는 다음과 같은 조건을 이용하여

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다.

다음과 같은 다중집합을 고려한 합집합과 교집합을 구해주도록 한다.

sum_union = sum([max(set_a.count(i), set_b.count(i)) for i in union])
sum_intersection = sum([min(set_a.count(i), set_b.count(i)) for i in intersection])

4. 주어진 조건대로 답을 구해준다.

# 정수부분만 출력
return math.floor((sum_intersection/sum_union) * 65536)

🎁 전체 풀이 코드

import math
def cut(ss, set_s):
    for i in range(len(ss)-1):
        if ss[i:i+2].isalpha():
            set_s.append(ss[i:i+2].lower())
    return set_s

def solution(str1, str2):
    set_a, set_b = [], []
    cut(str1, set_a)
    cut(str2, set_b)
    # 합집합
    union = set(set_a) | set(set_b)
    # 교집합
    intersection = set(set_a) & set(set_b)
    if len(union) == 0:
        return 65536
    
    sum_union = sum([max(set_a.count(i), set_b.count(i)) for i in union])
    sum_intersection = sum([min(set_a.count(i), set_b.count(i)) for i in intersection])
    
    return math.floor((sum_intersection/sum_union) * 65536)

🥇TIL

중복을 허용하는 다중집합을 구하는 방법을 익힐 수 있었다.

sum_union = sum([max(set_a.count(i), set_b.count(i)) for i in union])

문제를 충분히 읽어보고 놓치는 조건이 없도록 확인하도록 해야겠다.