[Lv2] 뉴스 클러스터링(python)

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/17677?language=python3 

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

 

2. 풀이 과정

- 다른 분들의 풀이를 참고하여 푼 문제. 다중 집합의 개념을 알게 되었다!

- 기존 집합 관련 문제는 set을 쓰기만 하면 되었었는데, 이번 문제는 set 자료구조의 기본 함수만을 사용할 수 없었기 때문에 버벅거렸다.  set의 기본 구현 방식도 익혀야 할 것 같다! 

 

3. 실수 한 것 & 새로 안 것

1) 다중집합 만드는 법

* set & counter 사용하기

- 기본 집합 연산에 사용되는 set은 중복을 허용하지 않는다. 따라서 collections.Counter를 이용해서 중복되는 개수를 허용하고 Counter의 교집합(&), 합집합(|)을 사용한다.

- Counter 메서드는 list의 원소값을 key값으로 하고, 원소의 갯수를 value값으로 하는 dictionary 형태의 구조를 가진다.

# 출처: https://jeongchul.tistory.com/661 [Jeongchul]
from collections import Counter
counter_1 = Counter(str1)
counter_2 = Counter(str2)
            
# 교집합
intersections = list((counter_1 & counter_2).elements)
 
 # 합집합 
unions = list((counter_1 | counter_2).elements)

 

* for문 사용하기

- 교집합 : arr_a 리스트의 요소가 arr_b리스트에 있다면, intersection에 해당 요소를 추가하고, 그 다음 요소를 비교하기 위해 arr_b리스트에서 해당 요소를 제거함

- 합집합 : arr_b 리스트의 복사본 arr_b1, arr_b2(union)를 만든다. arr_a 리스트의 요소가 arr_b1에 있다면 arr_b1에서 제거하고, 없다면 arr_b2에 추가한다. 

#교집합
intersection = []

for char1 in arr_a:
	if char1 in arr_b:
    	arr_b.remove(char1)
        intersection.append(char1)

#합집합
arr_b1 = arr_b.copy()
union = arr_b.copy()

for char in arr_a:
	if char1 not in arr_b1:
    	union.append(char1)
	else:
    	arr_b1.remove(char1)

 

* 일반 set & min / max 사용하기

- set 자료구조를 사용하여 교집합 / 합집합에 들어가는 요소를 구한다.

단, set은 중복 요소 개수를 알 수 없으므로 중복 요소 개수를 min,max로 구한다. 교집합에 char1이 포함된다 하면, 실제 교집합에서의 char1의 개수는 min(arr_a.count(char1), arr_b.count(char1))으로 알 수 있다. 반대로 합집합은 max()함수로 구할 수 있다.

gyo = set(arr_a) & set(arr_b)
hap = set(arr_a) | set(arr_b)

#교집합
intersects = []

for x in gyo:
	for _ in range(min(arr_a.count(x),arr_b.count(x)):
    	intersects.append(x)

#합집합
union = []
for x in hap:
	for _ in range(max(arr_a.count(x), arr_b.count(x)):
    	union.append(x)

 

2) list에서 알파벳만 남기기(띄어쓰기도 제거)

* re 모듈로 정규식 사용하기

- str1 = re.sub('[^a-zA-Z]',' ',str1).replace(" ","")

 

* isalpha함수 사용하기

- str = "".join([x for x in list(str1) if x.isalpha()])

- string형식 -> (각 문자를 떼서) list로 바꾼 후 isalpha()함수로 알파벳인 대상만 추출하여 list -> string으로 재변환

 

 

3) 나눗셈이 나온다면 항상 0 나누기를 주의하자! 

 

4) 이 문제처럼 answer = A / B 처럼 두 개 이상의 값을 구한 후 연산해야 한다면,

answer = A , answer /= B보단 각각 A,B를 구한 다음에 answer = A / B 형식으로 구하는 게 코드리뷰 면에선 좋은 듯

 

4. 코드

from collections import Counter

def solution(str1, str2):
    
    answer = 0
    
    #str1,str2의 영문자가 아닌 대상 삭제 및 소문자로 변경
    str1 = str1.lower()
    str2 = str2.lower()
    array_str1 = [ str1[i : i + 2] for i in range(len(str1) - 1) if str1[i : i + 2].isalpha() ]
    array_str2 = [ str2[i : i + 2] for i in range(len(str2) - 1) if str2[i : i + 2].isalpha() ]

    counter_1 = Counter(array_str1)
    counter_2 = Counter(array_str2)
            
    # 교집합
    intersections = list((counter_1 & counter_2).elements())

     # 합집합 
    unions = list((counter_1 | counter_2).elements())

    if len(unions) == 0:
        answer = 1
        
    else:
        answer = len(intersections) / len(unions)

    return int(answer * 65536)