[프로그래머스] 뉴스 클러스터링 - python

프로그래머스 문제 정복기

 

난이도 :  lv2

---

🔗 Link

---

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

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

📑 Summary

---

 입력받은 두 문자열을 각각 두글자씩 끊어서 다중 집합 원소를 만든다. 단, 영문으로만 된 글자만 취급하며, 대소문자는 신경쓰지 않는다. 그 뒤,원소의 중복을 허용하는 집합에서 '자키드 유사도'를 구하라. (자키드 유사도는 교집합 / 합집합 으로 정의된다.) 

 

🔑 How to solve? 

---

문제에서 요구하는 것을 거꾸로 생각해보자.

 

1. 자키드 유사도구하기
2. 자키드 = 교집합 / 합집합 이므로, 교집합과 합집합 구하기
3. 중복을 허용하는 다중 집합이므로, 중복에 대한 처리 신경쓰기
4. 다중집합을 만들기

 

이를 역순으로 진행하면 풀이는 끝난다.

 

다중집합 만들기

 중복을 포함하는 다중집합이기 때문에 무심코 set자료형으로 바꾸었다간 해당 집합이 몇개의 중복을 가지고 있는지 판단을 할 수가 없다. 이를 해결하기 위해 dict자료형을 이용했다. key값으로 집합의 요소를 두고, value로 갯수를 정리하면, 집합으로 사용하면서도, 중복된 갯수를 활용할 수 있다. 두 문자열을 아래의 함수를 통해 딕셔너리로 만든다.

 

 이 때, 문제에서는 영문자로만 된 다중집합만을 허용한다고 하였으므로, 정규식을 통해 검증한다.

아래의 정규식은 2글자로만 구성된 영문자를 판단하는 정규식이다.

 

# dict 형식으로 전환
def getDict(sten):
	#영문 판별 정규식
    p = re.compile(r'[a-zA-Z]{2}')
    data = dict()
    for i in range(len(sten)-1):
        #두글자가 모두 영문이라면
        if p.match(sten[i:i+2]):
            #소문자 통일
            key = (sten[i:i+2]).lower()
            #키가 존재한다면
            if data.get(key):
            	#값 추가
                data[key] +=1
            else:
            	#키 생성
                data[key]=1

    return data

 

중복을 허용하는 다중 집합 ?

 예를 들어, [1,1,1,2,3] 이라는 집합과 [1,2,3,3,3] 이라는 집합이 있다고 가정해보자. 해당 문제에서 다중집합은 앞의 두 집합을 다른 집합으로 본다. 두 집합의 교집합은 [1,2,3] 이지만, 합집합은 [1,1,1,2,3,3,3] 이다. 즉, 교집합은 작은 갯수(min),합집합은 큰 갯수(max)로 판단하면 된다. 이를 위해 위에서 다중집합을 딕셔너리 형태로 먼저 만든 것이다. 

 

 

교집합, 합집합 

 교집합이라면, 교집합 수행 후, 모든 요소들을 위에서 만든 딕셔너리에 비교하여 최소값을 넣어준다.

합집합이라면, 합집합 수행 후, 모든 요소들을 비교하여 최대값을 넣어준다. 

 

자키드 유사도 

 위를 통해 구한 교집합과 합집합을 통해 자키드 유사도 공식을 활용하면 된다. 단, 합집합이 0일 때는 유사도를 1로 정의하였으므로, 해당 조건만 처리한다면 문제를 해결 할 수 있다.

 

 

💡 Code

---

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


import re

def solution(str1, str2):
    answer = 0
    #2글자씩 끊어서 다중 집합 딕셔너리로 변환
    data1=getDict(str1)
    data2=getDict(str2)

	#편의를 위해 key값을 집합으로 따로 빼냄
    set1 = set(data1.keys())
    set2 = set(data2.keys())

    # print('교집합:',set1 & set2)
    # print('합집합:',set1 | set2)
    inter_num = getIntersectionCount(set1 & set2,data1,data2)
    union_num = getUnionCount(set1 | set2, data1,data2)


	# 합이 0일때는 1반환
    if union_num ==0 :
        res = 1
    else:
        res = inter_num/union_num
    
    #문제에서 요구한 후처리 수행
    answer = int(res * 65536)

    return answer
    
    
#합집합
def getUnionCount(union_data,data1,data2):
    union_cnt = 0
    for i in union_data:
    	#해당 요소가 data1에 없을 때
        if not data1.get(i):
            union_cnt+= data2[i]
        #해당 요소가 data2에 없을 때
        elif not data2.get(i):
            union_cnt+= data1[i]
        else:
        	#둘다 있는 요소라면, max값을 배치해야한다.
            union_cnt+= max(data1[i],data2[i])
    return union_cnt;

#교집합 
def getIntersectionCount(union_data,data1,data2):
    intersection_cnt = 0
    for i in union_data:
        intersection_cnt+= min(data1[i],data2[i])
    return intersection_cnt;

#dict전환 
def getDict(sten):
    p = re.compile(r'[a-zA-Z]{2}')
    data = dict()
    for i in range(len(sten)-1):
        if p.match(sten[i:i+2]):
            key = (sten[i:i+2]).lower()
            if data.get(key):
                data[key] +=1
            else:
                data[key]=1

    return data

 

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.