URL https://programmers.co.kr/learn/courses/30/lessons/17677#qna
문제 설명
- 뉴스 클러스터링
- 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. 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개 가지고 있다고 하자. 이 다중집합의 교집합 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가 된다.
- 이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 “FRANCE”와 “FRENCH”가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J(“FRANCE”, “FRENCH”) = 2/8 = 0.25가 된다.
입력 형식
- 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
- 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 “ab+”가 입력으로 들어오면, - “ab”만 다중집합의 원소로 삼고, “b+”는 버린다.
- 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. “AB”와 “Ab”, “ab”는 같은 원소로 취급한다.
출력 형식
- 입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
문제 풀이
- 일단, 코드가 많이 길고, 지저분함
- 주어진 str1과 str2는 소문자로 바꿔주고
- str1을 2개씩 모아서 isalpha를 사용하여 둘 다 알파벳일때만 temp에 저장
- str2을 2개씩 모아서 isalpha를 사용하여 둘 다 알파벳일때만 temp2에 저장
- temp와 temp2의 교집합을 구해준다. 교집합을 구할때 temp와 temp2의 길이를 확인해서 더 짧은쪽을 기준으로 교집합을 구하며 합집합을 구하기 위해 더 긴쪽에선 교집합의 원소를 remove해준다.
- 합집합은 temp1 + temp2 - 교집합인데 이미 교집합은 temp or temp2에서 교집합을 구할때 remove함 제거했했음
- 만일 합집합이 0이면 [len(union) = 0] 이면 에러가 나기때문에 1 * 65536을 리턴함
- 그 외는 (교집합 갯수 / 합집합 갯수) * 65536을 해줌
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def solution(str1, str2):
# 주어진 str1과 str2는 소문자로 바꿔주고
str1 = str1.lower()
str2 = str2.lower()
# str1을 2개씩 모아서 isalpha를 사용하여 둘 다 알파벳일때만 temp에 저장
temp = []
for i in range(0, len(str1)):
a = str1[i:i+2]
if len(a) == 2 and a.isalpha():
temp.append(a)
# str2을 2개씩 모아서 isalpha를 사용하여 둘 다 알파벳일때만 temp2에
temp2 = []
for i in range(0, len(str2)):
a = str2[i:i+2]
if len(a) == 2 and a.isalpha():
temp2.append(a)
# temp와 temp2의 교집합을 구해준다. 교집합을 구할때 temp와 temp2의 길이를 확인해서 더 짧은쪽을 기준으로 교집합을 구하며 합집합을 구하기 위해 더 긴쪽에선 교집합의 원소를 remove해준다.
inter = []
if len(temp) < len(temp2):
for s in temp:
if s in temp2:
inter.append(s)
temp2.remove(s)
else:
for s in temp2:
if s in temp:
inter.append(s)
temp.remove(s)
# 합집합 = temp1 + temp2 - inter (이미 inter는 temp or temp2에서 제거했음.)
union = temp + temp2
# 합집합이 0이면(둘은 공집합) 답은 1
if len(union) == 0:
return (1 * 65536)
else :
return(int((len(inter) / len(union)) * 65536))
1
2
3
str1 = 'FRANCE'
str2 = 'french'
solution(str1, str2)
1
16384
1
2
3
str1 = 'handshake'
str2 = 'shake hands'
solution(str1, str2)
1
65536
1
2
3
str1 = 'aa1+aa2'
str2 = 'AAAA12'
solution(str1, str2)
1
43690
1
2
3
str1 = 'E=M*C^2'
str2 = 'e=m*c^2'
solution(str1, str2)
1
65536