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

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

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

2018 KAKAO BLIND RECRUITMENT(카카오 공채 1차)에 나온 문제이다.

 

1. 대소문자 구별을 하지 않으므로 str1과 str2 모두 대문자로 변환한다.

 

2. str1을 돌며 두 글자씩 끊어서 다중집합의 원소로 만들고 A에 넣는다. 두 글자로 끊은 원소가 이미 A에 있다면 갯수를 1증가시키고 아니면 새로운 index를 만들어준다.

   (영문자가 아닌 다른 글자가 원소로 들어오면 버리므로 isalpha()함수를 사용해서 영문자만 걸러서 A에 넣었다.)

 

3. str2도 마찬가지로 B에 넣는다. A와 B에 원소가 하나씩 추가될 때마다 union을 1증가시켰다. 결과적으로 union은 A와 B의 총 집합개수이다.

 

4. 집합 A와 B가 모두 공집합일 때는 J(A, B)가 1이라고 했으므로 65536을 return해주고

   아닌 경우에는 A의 원소를 돌며 A의 원소가 B에 있다면 두 집합에 모두 존재하므로 원소의 개수 중 최솟값을 intersection에 더해준다.

 

5. 최종적으로 intersection에는 교집합의 개수가 들어오므로 교집합의 개수를 합집합의 개수(A와 B의 총 개수 - 교집합의 개수)로 나눈 값에 65536을 곱하고 소수점을 버린뒤 return 해준다.

 

def solution(str1, str2):
    intersection, union = 0, 0
    str1 = str1.upper()
    str2 = str2.upper()
    A, B = {}, {}
    for i in range(len(str1) - 1):
        news = str1[i] + str1[i + 1]
        if news.isalpha():
            if news in A:
                A[news] += 1
            else:
                A[news] = 1
            union += 1
    for i in range(len(str2) - 1):
        news = str2[i] + str2[i + 1]
        if news.isalpha():
            if news in B:
                B[news] += 1
            else:
                B[news] = 1
            union += 1
    
    if not A and not B:
        return 65536
    else:
        for i in A:
            if i in B:
                intersection += min(A[i], B[i])
            
    return int(65536 * (intersection / (union - intersection)))

 

(프로그래머스 level 2)