프로그래머스 LV2. 뉴스 클러스터링 (자바)

🍀 문제

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 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	answer
FRANCE	french	16384
handshake	shake hands	65536
aa1+aa2	AAAA12	43690
E=M*C^2	e=m*c^2	65536

 

 

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

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

 

 

😊 나의 코드

import java.util.*;
class Solution {
    public int solution(String str1, String str2) {
        double uni = 0; //합집합
        double inter = 0; //교집합
        HashMap<String, Integer> map = new HashMap();

        for(int i=1; i<str1.length(); i++) { //str1의 원소
            String s1 = "" + str1.charAt(i-1) + str1.charAt(i);
            s1 = s1.toLowerCase().replaceAll("[^a-z]", "");
            if(s1.length()==2){ // 문자열로만 이루어졌을때 원소 추가
                uni++; //합집합 수 1 증가하고 map에 담기
                if(map.containsKey(s1)) {
                    map.put(s1, map.get(s1)+1);
                }else {
                    map.put(s1,1);
                }
            }
        }

        for(int i=1; i<str2.length(); i++) { //str2의 원소
            String s2 = "" + str2.charAt(i-1) + str2.charAt(i);
            s2 = s2.toLowerCase().replaceAll("[^a-z]", "");
            if(s2.length()==2) { 
                if(map.containsKey(s2) && map.get(s2) >0) { //str1의 원소와 겹칠때
                    map.put(s2,  map.get(s2)-1);
                    inter++; //교집합 수 추가
                }else { //str1의 원소와 겹치지 않으면 합집합 개수 추가
                    uni++;
                }
            } 
        }

        if(uni==0) {
            return 65536;
        }

        int answer = (int) Math.floor((inter/uni)*65536);  
        return answer;
    }
}

 

 

우선 str1의 원소를 map에 담았다.

key : 원소, value : 원소의 중복 갯수

 

str2의 원소를 map과 비교하여 교집합, 합집합의 수를 증가시켰다.