[프로그래머스] Lv.2 뉴스클러스터링 - Python

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

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

---

• 생각
  • 다중집합에서 영어 대문자, 소문자 구분하지 않는다 했으니 모두 대문자로 바꾸기
  • 다중집합 만들면서 영어로만 되어있는게 아니면 버리기 : .isalpha()
  • 둘 다 공집합이면 1*65536
  • 둘 중 하나라도 공집합이면 교집합이 없으므로 0
  • 교집합/합집합 구하는 방법
    • 1.
      • 교집합 구하기
        • 원소에 중복을 허용하기에 set() 사용할 수 없음
        • 하나하나 비교하기
        • 원소 같은게 있으면 교집합에 넣고 str2관련 다중집합에서는 pop하기
          • 합집합을 위해
      • 합집합 구하기
        • 합집합 원소의 개수만 구하면 되니깐 길이로 계산
        • 교집합 + (str1관련 다중집합에만 있는 원소) + (str2관련 다중집합에만 있는 원소)
    • 2.
      • 교집합 set & set
      • 합집합 set | set
      • 중복값들이 제외되었으니 갯수세기
• 코드1

def solution(str1, str2): 
    # 모두 대문자로 바꾸기
    str1 = str1.upper()
    str2 = str2.upper()
    
    # 다중 집합 만들기
    # 영어로만 되어있는게 아니면 버리기
    one = []
    two = []
    for i in range(0,len(str1)-1):
        s = str1[i:i+2]
        if s.isalpha():
            one.append(s)
    for j in range(0,len(str2)-1):
        s = str2[j:j+2]
        if s.isalpha():
            two.append(s)

    # 둘 다 공집합이면
    if len(one) == len(two) == 0:
        return 65536
        
    # 한 쪽이 공집합
    elif len(one) == 0 or len(two) == 0: 
        return 0
    
    one.sort()
    two.sort()
    
    # 교집합
    intersection = []
    
    for a in range(len(one)):
        for b in range(len(two)):
            if one[a] == two[b]:
                intersection.append(one[a])
                two.pop(b)
                break
    
    # 합집합
    union_length = len(intersection) + (len(one) - len(intersection)) + (len(two))
    
    # 교집합 수/합집합 수
    answer = len(intersection)/union_length
    return int(answer * 65536)

 

• 코드2

import math

def solution(str1, str2):
	# 다중 집합 만들기 / 영어로만 이루어진
    str1 = [str1[i:i+2].upper() for i in range(0, len(str1)-1) if str1[i:i+2].isalpha()]
    str2 = [str2[i:i+2].upper() for i in range(0, len(str2)-1) if str2[i:i+2].isalpha()]
	
    # 교집합 / 합집합 구하기(중복제외)
    gyo = set(str1) & set(str2)
    hap = set(str1) | set(str2)
	
    # 둘 다 공집합이면 합집합의 길이가 0
    if len(hap) == 0 :
        return 65536
	
    # 중복된 원소가 필요하니
    # 교집합은 중복된 원소가 양쪽 중 더 적게 가진 수 사용
    # 합집합은 중복된 원소가 양쪽 중 더 많이 가진 수 사용
    gyo_sum = sum([min(str1.count(gg), str2.count(gg)) for gg in gyo])
    hap_sum = sum([max(str1.count(hh), str2.count(hh)) for hh in hap])

    return math.floor((gyo_sum/hap_sum)*65536)