[알고리즘] 뉴스 클러스터

프로그래머스 2018 KAKAO BLIND RECRUITMENT 코딩테스트에서 출제된 문제

뉴스 클러스터 문제

1.두 글자씩 자른 리스트 만들기

FRANCE => 'FR','RA','AN','NC','CE'

두 글자씩 끊어서 다중집합을 만드는 방식이므로 1씩 증가하며 두 글자를 만든다.

---

2.자카드 유사도 계산

자카드 유사도는 두 문자열의 (교집합)/(합집합)이다.

교집합 구하기

str1 ['AA', 'AA']
str2 ['AA', 'AA', 'AA']

위의 두 문자열은 다 같지만 교집합은 2이다.
str1의 길이 * st2의 길이만큼 문자열 비교를 진행하지만
str2의 길이만큼 dy리스트를 만들어서 st1와 st2의 같은 부분이 있으면 str2에 표시를 한다. 그림과 같은 경우

합집합 구하기

합집합은 str1의 길이 + str2의 길이 - 교집합 개수(중복 제거)로 구할 수 있다.

---

코드

def solution(str1, str2):
    answer = 65536
    st1, st2 = [], []
    for i in range(len(str1)-1): # ①
        if str1[i].isalpha() and str1[i+1].isalpha():
            st1.append(str1[i:i+2].upper()) 
    for i in range(len(str2)-1): # ①
        if str2[i].isalpha() and str2[i+1].isalpha():
            st2.append(str2[i:i+2].upper())
            
    dy = [0]*len(st2)
    for i in range(len(st1)): # ②
        for j in range(len(st2)):
            if st1[i]==st2[j] and dy[j]==0:
                dy[j]=1
                break

    n = sum(dy)
    u = len(st1)+len(st2)-n # ②
    
    if u==0 and n==0: return answer
    else: return int(answer*(n/u))