[파이썬] 프로그래머스 - [1차] 뉴스 클러스터링

문제 설명

 

생각한 문제 풀이법

1. str1 집합, str2 집합을 구현한다.

2. 교집합과 합집합을 규칙에 맞게 구현한다.

3. 다중 원소 규칙을 지키기 위해서 교집합과 합집합을 만들 때 겹치는 값의 최소 빈도 값은 교집합에 넣고, 최다 빈도 값은 합집합에 넣는다.

4. 빈도 값을 더해서 집합의 크기를 구해 계산한다.

 

def solution(str1, str2):
    # 규칙 : 대문자와 소문자 차이는 무시한다.
    str1 = str1.lower()
    str2 = str2.lower()
    str1_set = []           # str1의 집합
    str2_set = []           # str2의 집합
    intersection = []       # 교집합
    union = []              # 합집합
    previous_word_i = []    # 교집합 구할 때, 중복 방지
    previous_word_u = []    # 합집합 구할 때, 중복 방지
    intersection_count = 0  # 교집합 크기
    union_count = 0         # 합집합 크기
    
    # 집합을 구하는 과정
    for i in range(len(str1)-1):
        if str1[i].isalpha() and str1[i+1].isalpha():
            str1_set.append(str1[i] + str1[i+1])
    
    for i in range(len(str2)-1):
        if str2[i].isalpha() and str2[i+1].isalpha():
            str2_set.append(str2[i] + str2[i+1])

    # 집합 두개가 모두 공집합일 경우
    if len(str1_set) == 0 and len(str2_set) == 0:
        return 65536
    # 둘 중 작은 집합을 str1_set으로 설정
    elif len(str1_set) > len(str2_set):
        str1_set, str2_set = str2_set, str1_set

    # 교집합을 구하는 과정
    for i in range(len(str1_set)):
        if str1_set[i] in str2_set:
            if str1_set[i] in previous_word_i:
                continue
            str1_count = str1_set.count(str1_set[i])
            str2_count = str2_set.count(str1_set[i])
            intersection.append([str1_set[i], min(str1_count, str2_count)])
            previous_word_i.append(str1_set[i])

    # 합집합을 구하는 과정
    for i in range(len(str1_set)):
        if str1_set[i] in str2_set:
            if str1_set[i] in previous_word_u:
                continue
            str1_count = str1_set.count(str1_set[i])
            str2_count = str2_set.count(str1_set[i])
            union.append([str1_set[i], max(str1_count, str2_count)])
            previous_word_u.append(str1_set[i])
        else:
            union.append([str1_set[i], 1])
    
    
    for i in range(len(str2_set)):
        if str2_set[i] not in previous_word_u:
            union.append([str2_set[i], 1])
    
    # 교집합 크기 구하기
    for i in range(len(intersection)):
        intersection_count += intersection[i][1]
    
    # 합집합 크기 구하기
    for i in range(len(union)):
        union_count += union[i][1]    
    
    return int(intersection_count / union_count * 65536)