[파이썬] 뉴스 클러스터링 - 2018 KAKAO BLIND RECRUITMENT [CODING TEST #17]

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

 

 

설명이 좀 긴데, 두 글자씩 끊어서 다중집합을 만들고 교집합 / 합집합을 계산하는 코드를 짜는 문제이다.

아래는 꼭 구현해야 할 제한사항이다.

• 영문자는 대소문자를 구분하지 않음. Ab와 ab는 같은 원소로 취급한다.
• 영문자 이외에 문자,숫자가 포함된 다중집합 원소는 제거된다.
• 두 집합이 모두 공집합이면 J(A,B) = 1이다.

 

교집합을 저장할 inter 리스트와, 합집합을 저장할 sum_ 딕셔너리를 선언했다. 합집합에 대해서 딕셔너리를 쓰는 이유는 원소가 중복이 가능하기 때문에 원소마다의 빈도수를 저장해야 하기 때문이다.

str1의 원소들을 sum_['원소'] 값을 1 증가시키도록 하여 합집합에 모두 넣는다. 그 다음, str2의 원소를 따로 셀 sum_for_str2 딕셔너리를 이용하여 str의 원소들을 교집합이나 합집합에 넣는다.

• sum_['원소'] > sum_for_str2['원소'] 이면, str1에 나타난 중복 원소가 str2보다 많은 상태이다. 따라서 교집합에 해당 원소가 추가된다. 
• sum_['원소'] = sum_for_str2['원소'] 이면, str2에 나타난 중복 원소가 더 많은 상태이다. 이 때에는 합집합에 해당 원소가 추가되며, sum_['원소'] 가 1 증가한다.
• 위의 둘 중 하나의 조건문을 통과하고 난 뒤 sum_for_str2['원소']가 1 증가한다. (따라서 str2에 중복 원소가 계속 등장해도 두 번째 조건문에 계속 해당되어 합집합에 원소가 추가된다.)

sum_.items()를 돌면서 합집합 총 원소 개수를 구하고, 계산하면 끝이다. 버림은 math.floor(x)를 이용했다.

 

from collections import defaultdict
import math
def solution(str1, str2):
    # 알파벳 소문자로 통일
    str1 = str1.lower()
    str2 = str2.lower()
    
    inter = [] # 교집합
    sum_ = defaultdict(int) # 합집합
    sum_for_str2 = defaultdict(int) # str2에서 사용하기 위한 dict
    
    # str1 : sum_ 딕셔너리에 count
    for index, alpha in enumerate(str1):
        if index > 0 and str1[index-1].isalpha() and alpha.isalpha():
            sum_[str1[index-1] + alpha] += 1
            
    # str2 : sum_for_str2에 따로 저장하면서, sum_보다 작으면 교집합에 추가 / 크면 합집합에 추가.
    for index, alpha in enumerate(str2):
        if index > 0 and str2[index-1].isalpha() and alpha.isalpha():
            if sum_[str2[index-1]+alpha] > sum_for_str2[str2[index-1]+alpha] : # 교집합 case
                inter.append(str2[index-1]+alpha)                   
            else : # str1보다 str2에 많은 경우 : 합집합 case
                sum_[str2[index-1]+alpha] += 1
            sum_for_str2[str2[index-1]+alpha] += 1
    
    sum_count = 0
    for item in sum_.items(): # 합집합 원소 개수 count
        sum_count += item[1]
    
    # 두 집합이 모두 공집합인 case
    if sum_count==0:
        answer = 65536
    # 일반적인 case : math.floor()로 소수점 버림
    else :
        answer = math.floor((len(inter)/sum_count)*65536)        
    return answer

 

금방 풀 줄 알았는데 조건 따지는게 생각보다 어려웠다..