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

Posted on | In |

오늘의 문제

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

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

입력형식

  1. 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
  2. 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 ab+가 입력으로 들어오면, ab만 다중집합의 원소로 삼고, b+는 버린다.
  3. 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. AB와 Ab, ab는 같은 원소로 취급한다.

풀이 방법

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def J(A, B):
    a = set(A)
    b = set(B)
    intersec = a.intersection(b)
    union = a.union(b)
    
    result = 1 if len(union) == 0 else sum([min(A.count(i), B.count(i)) for i in intersec]) \
    / sum([max(A.count(i), B.count(i)) for i in union])
    
    return int(result * 65536)


def solution(str1, str2):
    str1, str2 = str1.upper(), str2.upper()
    
    str1_list = [(str1[i-1]+str1[i]) for i in range(1, len(str1)) if (str1[i-1]+str1[i]).isalpha() == True]
    str2_list = [(str2[i-1]+str2[i]) for i in range(1, len(str2)) if (str2[i-1]+str2[i]).isalpha() == True]
    
    return J(str1_list, str2_list)

원소의 개수만을 알면 자카드 유사도를 계산할 수 있기 때문에 이부분에 유념하면 된다.

사담

근데 지금 봐도 모르겠다 나중에 다시 한 번 풀어볼만한 문제인듯

함수를 두 개로 나눈 이유는… 사실 문제에 J(A, B)라고 써있는게 멋있었기 때문 … ㅎ

젤 고생했던 부분이 min, max 부분이었는데 문제에 걍 나와있어서 막판에 보고 풀었당

1
자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 `A`는 원소 1을 3개 가지고 있고, 다중집합 `B`는 원소 1을 5개 가지고 있다고 하자. 이 다중집합의 교집합 `A ∩ B`는 원소 1을 min(3, 5)인 3개, 합집합 `A ∪ B`는 원소 1을 max(3, 5)인 5개 가지게 된다. 다중집합 `A` = {1, 1, 2, 2, 3}, 다중집합 `B` = {1, 2, 2, 4, 5}라고 하면, 교집합 `A ∩ B` = {1, 2, 2}, 합집합 `A ∪ B` = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 `J(A, B)` = 3/7, 약 0.42가 된다.