2018 카카오 코딩테스트 1차 뉴스 클러스터링 JS 문제풀이

🔗직접 문제 풀러가기

 

 

문제

 

두 문자열을 자카드 유사도를 구하라.

 

• J(A,B) = 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값.
• 두 집합이 공집합일 경우 나눗셈 정의가 안되므로 J(A,B) = 1 을 따로 정의하라.

 

입력값

• 2 < str1, str2 <= 1000
• 입력값인 두 문자열을 2글자 씩 끊어 중복이 허용되는 다중집합 원소로 만들어라.
• 영문자로 된 글자 쌍만 유효하다. 기타 공백이나 숫자 특수문자가 있는 경우 그 글자 쌍을 버린다.
• AB == ab == Ab == aB 대소문자 차이는 무시한다.

 

 

출력값

• 0 - 1 사이 실수에 65536 곱한 후 정수부만 출력.

 

 

 

 

문제풀이

 

 

우선 문자열에서 원소를 뽑아 원소 - 원소갯수를 매핑하는 함수 tokenize를 정의했다. 문제풀이의 편의상 token들의 총 갯수도 함께 반환했다. 

'A집합 + B집합 - A와 B의 교집합 = 합집합'이므로 교집합의 크기만 구했다.

 

 

시간복잡도: O(s1 + s2)

공간복잡도: O(s1 + s2)