[Programmers] 2018 KAKAO BLIND RECRUITMENT[1차] 뉴스 클러스터링

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

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

문자열에 등장하는 알파벳으로만 이루어진 부분 문자열들을 추출해내고, 해당 알파벳들을 집합으로 만들어 교집합을 구하는 문제이다.

문제에 등장하는 자카드 유사도는 교집합의 크기 / 합집합의 크기로 정의되는데, 합집합은 각각의 집합의 크기와 교집합으로 다시 정의할 수 있으므로 교집합만 구해주면 된다

처음에는 set 자료형을 쓸까 하다가 중복 원소를 포함할 수 있다고 해서, list로 관리해주며 공통된 원소가 등장할 경우 삭제하는 방식으로 구현했는데

for문 중간에 remove를 하면 끝까지 반복하지 않아서(삭제한 만큼 덜 반복해서) 그냥 boolean, int 이차원 list로 관리해주고 사용 여부를 체크해주었다

def solution(str1, str2):
    answer = 0
    u=[]
    v=[]
    for i in range(0,len(str1)-1):
        st=str1[i:i+2]
        if st.isalpha():
            u.append([st.lower(),True])
    for i in range(0,len(str2)-1):
        st=str2[i:i+2]
        if st.isalpha():
            v.append([st.lower(),True])
    answer=len(u)+len(v)
    inter=0
    for i in u:
        for j in v:
            if i==j:
                i[1]=False
                j[1]=False
                inter+=1
    if answer==inter: return 65536
    answer=int((inter/(answer-inter))*65536)
    return answer