1. 문제
1) 문제 링크
: https://programmers.co.kr/learn/courses/30/lessons/17677
코딩테스트 연습 - [1차] 뉴스 클러스터링
뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브
programmers.co.kr
2) 설명
자카드 유사도를 활용해 두 문자열의 유사도를 비교하는 문제다
자카드 유사도에 대한 자세한 설명은 문제 링크에 있다
2. 풀이
1) 알고리즘
: 집합?
2) 풀이 설명
C++로 sstream 사용해서 풀어도 되긴 하는데 파이썬으로 풀기에 너무 적합한 문제 같아서 그냥 파이썬으로 풀어봤다.
일단 소문자 대문자를 가리지 않기 때문에 문자열을 다 소문자로 변환했다.
그리고 각 문자열을 두 글자씩 떼서 리스트를 만든다. 이때 특수문자가 포함되어 있으면 건너뛴다.
이제 n(교집합) / n(합집합) 을 구하면 된다.(마지막에 한 번만 곱해주면 되기 때문에 65536을 곱하는 건 일단 생략하겠다...)
n(A U B) = n(A) + n(B) - n(A ^ B) // n(A ^ B)는 A B 교집합
공식을 이용한다.
교집합을 구하는 건 str1_arr(str1에서 두 글자씩 떼어낸 문자열 집합)에 있는 문자열 중 str2_arr(str2에서 두 글자씩 떼어낸 문자열 집합)에 있는 것들만 카운팅해준다. 카운팅하면 str2_arr에서 그 문자열은 빼줘야 한다. 왜냐하면 다음과 같은 경우를 방지하기 위해서다.
str1_arr = {1, 1, 1}
str2_arr = {1, 2, 3}
일 때 처음 1을 카운팅해주고 str2_arr에서 빼주지 않으면 두 번째, 세 번째 1에서도 str2_arr에 1 값이 있기 때문에 교집합의 개수가 3이 되기 때문이다.
여튼 그렇게 교집합의 개수를 구했으면 공식 따라서 자카드 유사도를 구해주면 된다.
3. 코드
def solution(str1, str2):
mul_val = 65536
# 소문자 변환
str1 = str1.lower()
str2 = str2.lower()
# 두글자씩 떼어서 배열로 변환
str1_arr = [ str1[i : i + 2] for i in range(len(str1) - 1) if str1[i : i + 2].isalpha() ]
str2_arr = [ str2[i : i + 2] for i in range(len(str2) - 1) if str2[i : i + 2].isalpha() ]
union_count = len(str1_arr) + len(str2_arr) # (A U B) = (A) + (B) - (A ^ B) 공식 사용 : 교집합 개수 구한 후 빼줘야 함
# 교집합 개수 구하기
intersection_count = 0
for x in str1_arr:
if x in str2_arr:
intersection_count += 1
str2_arr.remove(x)
# 합집합 개수 구하기
union_count -= intersection_count # 교집합 개수 빼주기
if union_count == 0:
return mul_val
else:
return int(intersection_count / union_count * mul_val)
4. 느낀점
리스트 컴프리헨션 최고!
문자열에 isalpha()라는 함수가 있다는 걸 처음 알았다..
Counter라는 걸 사용하면 교집합 합집합을 더 쉽게 구할 수 있는 것 같다. 틈 나면 공부해보자!(보통 이러면 안 한다)
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [LV4] 4단 고음 (0) | 2021.08.19 |
|---|---|
| [LV3] 불량 사용자 (0) | 2021.08.13 |
| [LV4] 호텔 방 배정 (0) | 2021.08.13 |
| [LV2] 거리두기 확인하기 (0) | 2021.07.29 |