중복을 허용하는 집합 다루기

1. 문제

 

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

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

 

 

여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. 

 

Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다.

 

개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 "카카오 신입 개발자 공채" 관련 기사를 검색해보았다.

 

카카오 첫 공채...'블라인드'방식 채용

 

카카오, 합병 후 첫 공채... 블라인드 전형으로 개발자 채용

 

카카오, 블라인드 전형으로 신입 개발자 공채

 

카카오 공채, 신입 개발자 코딩 능력만 본다

 

카카오, 신입 공채... "코딩 실력만 본다"

 

카카오 "코딩 능력만으로 2018 신입 개발자 뽑는다"

 

기사의 제목을 기준으로 "블라인드 전형"에 주목하는 기사와 "코딩 테스트"에 주목하는 기사로 나뉘는 걸 발견했다.

 

튜브는 이들을 각각 묶어서 보여주면 카카오 공채 관련 기사를 찾아보는 사용자에게 유용할 듯싶었다

 

유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 "자카드 유사도"라는 방법을 찾아냈다.

 

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다.

 

두 집합 A,B 사이의 자카드 유사도 J(A,B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

 

예를 들어 집합 A={1,2,3}, 집합 B={2,3,4}라고 할때, A,B의 교집합 = {2,3}이고 A,B의 합집합 = {1,2,3,4}이므로

 

집합 A,B사이의 자카드 유사도 J(A,B)=2/4=0.5가 된다.

 

집합 A,B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A,B)=1로 정의한다

 

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 1을 3개 가지고 있고

 

다중집합 B는 원소 1을 5개 가지고 있다고 하자.

 

이 다중집합의 교집합은 원소 1을 min(3,5)인 3개, 합집합은 원소 1을 max(3,5)인 5개 가지게 된다.

 

다중집합 A={1,1,2,2,3}이고 B={1,2,2,4,5}라고 하면 A,B의 교집합은 {1,2,2}이고 합집합은 {1,1,2,2,3,4,5}가 되므로 자카드 유사도 J(A,B)=3/7로 약 0.42가 된다

 

이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다.

 

문자열 "FRANCE"와 "FRENCH"가 주어진다고 하자. 이를 두 글자씩 끊어서 다중집합을 만들 수 있다.

 

각각 {FR,RA,AN,NC,CE}와 {FR,RE,EN,NC,CH}가 되며 교집합은 {FR,NC}, 합집합은 {FR,RA,AN,NC,CE,RE,EN,CH}가 되므로 두 문자열 사이의 자카드 유사도는 2/8=0.25가 된다.

 

2. 입출력

 

입력으로는 str1과 str2의 두 문자열이고 각 문자열 길이는 2이상 1000이하

 

입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다.

 

이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수문자가 들어있는 경우는 그 글자쌍을 버린다.

 

예를 들어 "ab+"가 입력으로 들어오면 "ab"만 다중집합의 원소로 삼고 "b+"는 버린다.

 

다중집합의 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다.

 

"AB"와 "Ab"와 "ab"는 같은 원소로 취급한다.

 

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

 

3. 예시

 

 

4. 나의 풀이

 

먼저 대소문자를 구분하지 않고 비교를 한다고 했으니까 주어진 문자열을 소문자화시킨다

 

lower() 메소드는 주어진 문자열에서 알파벳을 소문자로 만든다

 

여기서 공백이나 특수문자, 숫자는 무시한다

 

def solution(str1,str2):
    
    answer = 0
    
    str1 = str1.lower()
    
    str2 = str2.lower()
    
    print(str1,str2)

handshake shake hands
aa1+aa2 aa12
e=m*c^2 e=m*c^2

 

예시로 print한 결과를 보면 lower는 숫자나 특수문자 공백과 상관없이 알파벳만 소문자로 만들었다

 

다음으로 두글자씩 끊어서 다중집합을 만든다

 

두글자씩 끊어서 순회하는 2-gram 방법은 이미 앞에서 배운바 있다

 

list(zip(*[str[i:] for i in range(2)])) 이런식으로

 

def solution(str1,str2):
    
    answer = 0
    
    str1 = str1.lower()
    
    str2 = str2.lower()
    
    a_two_gram = list(zip(*[str1[i:] for i in range(2)]))
    
    b_two_gram = list(zip(*[str2[i:] for i in range(2)]))
    
[('e', '='), ('=', 'm'), ('m', '*'), ('*', 'c'), ('c', '^'), ('^', '2')] 
[('e', '='), ('=', 'm'), ('m', '*'), ('*', 'c'), ('c', '^'), ('^', '2')]

 

마지막 예시 E=M*C^2 이거 프린트해보면 위와 같이 튜플 리스트로 나온다

 

두글자씩 붙인 2-gram 리스트로 만들려면 ''.join()을 이용해서 붙여줘야한다

 

def solution(str1,str2):
    
    answer = 0
    
    str1 = str1.lower()
    
    str2 = str2.lower()
    
    a_two_gram = list(zip(*[str1[i:] for i in range(2)]))
    
    b_two_gram = list(zip(*[str2[i:] for i in range(2)]))
    
    a_two_gram_list = [''.join(a) for a in a_two_gram]
    
    b_two_gram_list = [''.join(b) for b in b_two_gram]
    
['e=', '=m', 'm*', '*c', 'c^', '^2'] 
['e=', '=m', 'm*', '*c', 'c^', '^2']

 

그러면 위와 같이 2-gram 리스트로 나온다

 

그러면 이제 알파벳이외의 공백이나 특수문자, 숫자가 들어간 문자쌍은 제거하라고 했는데

 

isalpha()를 이용하면 된다

 

적어도 하나 이상의 문자로 구성되어 있는 문자열의 모든 문자가 알파벳이라면 True를 return한다

 

 

그래서 two_gram_list를 순회하여 isalpha()가 True인 원소만 리스트에 담는다

 

중복된 원소를 허용하는 집합을 다루고자 하므로 set이 아니고 list에 담아야한다

 

def solution(str1,str2):
    
    answer = 0
    
    str1 = str1.lower()
    
    str2 = str2.lower()
    
    a_two_gram = list(zip(*[str1[i:] for i in range(2)]))
    
    b_two_gram = list(zip(*[str2[i:] for i in range(2)]))
    
    a_two_gram_list = [''.join(a) for a in a_two_gram]
    
    b_two_gram_list = [''.join(b) for b in b_two_gram]
    
    A = [a for a in a_two_gram_list if a.isalpha()]
    
    B = [b for b in b_two_gram_list if b.isalpha()]

 

다음으로 교집합과 합집합을 구해야한다

 

근데 리스트끼리 덧셈이나 뺼셈 지원하는 것도 아니고 그렇다고 set으로 바꾸면 중복된 원소를 다룰수 없어서 어려워지고

 

교집합이 무엇인가를 생각을 해보면

 

두 집합이 모두 가지고 있는 원소로 구성된 집합이다

 

그러면 A에서 원소 하나씩 순회를 해서 a라고 해보면 이 a가 B에 들어가 있으면 교집합에 집어넣는다

 

-------------------------------------------------------------------------------------------------------------

근데 단순히 이렇게만 하면 문제가 A = {1,1,2,2,3}과 B = {1,2,2,4,5}를 생각해보면

 

먼저 1은 B에 있으니까 교집합 {1}

 

다음 1이 B에 있으니까 교집합 {1,1}

 

다음 2가 B에 있으니까 교집합 {1,1,2}

 

다음 2가 B에 있으니까 교집합 {1,1,2,2}

 

다음 3은 B에 없으니까 교집합은 {1,1,2,2}로 나오는데

 

그러나 실제 교집합은 {1,2,2}이다

 

그래서 한번 B에 들어가있는 원소를 찾았으면 B에서 그 원소를 제거해야한다

 

------------------------------------------------------------------------------------------------

 

def solution(str1,str2):
    
    answer = 0
    
    str1 = str1.lower()
    
    str2 = str2.lower()
    
    a_two_gram = list(zip(*[str1[i:] for i in range(2)]))
    
    b_two_gram = list(zip(*[str2[i:] for i in range(2)]))
    
    a_two_gram_list = [''.join(a) for a in a_two_gram]
    
    b_two_gram_list = [''.join(b) for b in b_two_gram]
    
    A = [a for a in a_two_gram_list if a.isalpha()]
    
    B = [b for b in b_two_gram_list if b.isalpha()]
    
    inter_a_b = []
    
    n_A = len(A)
    
    n_B = len(B)
    
    for a in A:
        
        if a in B:
        
            inter_a_b.append(a)
            
            B.pop(B.index(a)) #B.remove(a)

 

교집합을 inter_a_b = []라 하고 A,B의 길이는 A,B의 원소의 수니까 일단 미리 구해놓는다

 

다음 A의 원소를 순회해서 a라 하고 B에 들어가있다면 교집합 inter_a_b에 넣는다

 

그리고 B에서 해당 a의 원소를 찾아 제거한다.

 

B.pop(B.index(a))를 하면 제거할 수 있다

 

혹은 B.remove(a)해도 바로 제거할 수 있다

 

다음 합집합을 구해야하는데 합집합의 원소의 수는 A의 원소의 수 + B의 원소의 수 - A,B의 교집합의 원소의 수 이다

 

def solution(str1,str2):
    
    answer = 0
    
    str1 = str1.lower()
    
    str2 = str2.lower()
    
    a_two_gram = list(zip(*[str1[i:] for i in range(2)]))
    
    b_two_gram = list(zip(*[str2[i:] for i in range(2)]))
    
    a_two_gram_list = [''.join(a) for a in a_two_gram]
    
    b_two_gram_list = [''.join(b) for b in b_two_gram]
    
    A = [a for a in a_two_gram_list if a.isalpha()]
    
    B = [b for b in b_two_gram_list if b.isalpha()]
    
    inter_a_b = []
    
    n_A = len(A)
    
    n_B = len(B)
    
    for a in A:
        
        if a in B:
        
            inter_a_b.append(a)
            
            B.pop(B.index(a)) #B.remove(a)
    
    union_a_b = n_A+n_B-len(inter_a_b)
    
    if union_a_b == 0:
    
       answer = 65536
   
    else:
        
        answer = int(65536*len(inter_a_b)/union_a_b)
    
    return answer

 

다음 정답을 구해야하는데 두 집합이 모두 공집합이면 자카드 유사도는 1로 정의한다고 했으므로 합집합의 원소의 수가 0이면 65536으로 바로 return하고

 

그렇지 않으면 자카드 유사도에 65536을 곱하고 소수부는 제거하라했으므로 int()함수를 씌워준다

 

 

5. 다른 풀이

 

좋아요를 가장 많이 받은 풀이를 살펴보면

 

import re
import math

def solution(str1, str2):
    str1 = [str1[i:i+2].lower() for i in range(0, len(str1)-1) if not re.findall('[^a-zA-Z]+', str1[i:i+2])]
    str2 = [str2[i:i+2].lower() for i in range(0, len(str2)-1) if not re.findall('[^a-zA-Z]+', str2[i:i+2])]

    gyo = set(str1) & set(str2)
    hap = set(str1) | set(str2)

    if len(hap) == 0 :
        return 65536

    gyo_sum = sum([min(str1.count(gg), str2.count(gg)) for gg in gyo])
    hap_sum = sum([max(str1.count(hh), str2.count(hh)) for hh in hap])

    return math.floor((gyo_sum/hap_sum)*65536)

 

[^a-zA-Z]+ 이게 무슨 의미인가?

 

[^a-zA-Z]는 영문자가 아닌 것

 

+는 1번 이상

 

그래서 re.findall('[^a-zA-Z]+', str1[i:i+2]은 str1[i:i+2]에서 영문자가 아닌 것이 1문자 이상인 경우를 모두 찾는다

 

그러면 if not이니까 for문에서 0부터 len(str1)-1까지 순회를 하는데 str1[i:i+2]에 대하여

 

영문자가 아닌 것이 1문자 이상인 경우가 아니라면 .lower()을 붙이고 리스트에 집어넣는다

 

--------------------------------------------------------------------------------------------------------------------------------

다음 교집합과 합집합이 재밌는데 교집합과 합집합을 굳이 구하지 않고 원소의 수만 구하면 된다는 점에 주목한 것 같다

 

교집합과 합집합을 가장 쉽게 구하는 방법은 역시 set으로 바꾸고 &와 | 기호를 사용하여 구할 수 있을것인데

 

그렇게 set으로 구한 교집합과 합집합에 대하여 원소를 순회하고 str1과 str2에서 각각 몇개인지 구해본다음에

 

최솟값이 교집합의 원소의 수가 되고 최댓값이 합집합의 원소의 수가 된다

 

예를 들어서 생각을 해보면 A = {1,1,2,2,3}과 B = {1,2,2,4,5}라고 해보자

 

A를 set으로 바꾸고 B를 set으로 바꾸면 {1,2,3}과 {1,2,4,5}가 된다.

 

그러면 교집합은 {1,2}이고 합집합은 {1,2,3,4,5}가 된다

 

이 교집합의 원소 {1,2}에 대하여 A와 B에서 각각 몇개가 들어가있는지 세본다

 

1은 A에서 2개이고 B는 1개 있는데 여기서 최솟값은? 1이다.

 

2는 A에서 2개 있고 B는 2개 있는데 여기서 최솟값은? 2이다.

 

그래서 set으로 바꾸지 않고 A,B의 교집합은 {1,2,2}

 

합집합도 생각을 해보면 {1,2,3,4,5}에 대하여 A,B에 각각 몇개가 있는지 세본다

 

1은 A에서 2개 B에서 1개 있는데 최댓값은 2

 

2는 A에서 2개 B에서 2개 있는데 최댓값은 2

 

나머지는 모두 각각 1개,0개씩 있고 최댓값은 1

 

그래서 A,B의 합집합은 {1,1,2,2,3,4,5}가 된다

--------------------------------------------------------------------------------------------------------------------------

 

 

6. 되돌아보기

 

n-gram 순회하는 방법 다시 복습하는 겸 기억하면 좋고

 

isalpha랑 lower같은 메소드는 언제나 기억하고 있으면 좋다

 

교집합과 합집합에 대해서...

 

교집합 구할때 A에서 순회하여 B에 들어가있는지 검사해서 집어넣는데 중요한 점은 집어넣은 원소는

 

B에서 제거해야한다는 점

 

원소의 수만 주목한다면 A,B를 set으로 바꾸고 교집합 합집합을 구하고 각각에서 순회하여 A,B에서 개수를 세서

 

최솟값이 교집합의 원소의 수가 되고 최댓값이 합집합의 원소의 수가 된다는 다른 풀이에서 쓴 트릭도 눈여겨볼만하다