[Programmers] [1차] 뉴스 클러스터링

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

프로그래머스

문제 설명

자카드 유사도를 구해서 반환하면 되는 문제이다. 주어진 문자열을 두 글자씩 잘라서 다중집합을 만들고 합집합과 교집합의 크기를 구한 뒤 65536을 곱하고 정수 처리하여 반환하면 된다. 이때 영문자를 제외한 글자가 포함되어 있다면 그 문자는 버린다. 여기서 주의할 점은 다중집합이다. 처음엔 단순 집합인줄 알고 HashSet으로 구했다가 문제를 다시 읽어보니 중복이 포함되어 있었다. 그래서 HashSet 대신 HashMap으로 문제를 해결했다. 문제를 해결하는 순서는 다음과 같다.

1. 영문자로만 구성된 다중 집합을 만든다.
2. 합집합의 크기를 구한다.
3. 교집합의 크기를 구한다.
4. 자카드 유사도를 구한다.

코드

import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(String str1, String str2) {
        str1 = str1.toLowerCase(); str2 = str2.toLowerCase();
        
        Map<String, Integer> set1 = createMultiSet(str1);
        Map<String, Integer> set2 = createMultiSet(str2);
        
        int unionSize = getUnionSize(set1, set2);
        int intersectionSize = getIntersectionSize(set1, set2);
        
        double jaccardSimilarity = getJaccardSimilarity(unionSize, intersectionSize);
        int answer = (int) Math.floor(jaccardSimilarity * 65536);
        
        return answer;
    }
    
    private double getJaccardSimilarity(int unionSize, int intersectionSize) {
        if (unionSize == 0 && intersectionSize == 0) {
            return 1;
        }
        
        return (double) intersectionSize / unionSize;
    }
    
    private int getIntersectionSize(Map<String, Integer> set1, Map<String, Integer> set2) {
        int result = 0;
        
        Set<String> intersection = new HashSet<>(set1.keySet());
        intersection.retainAll(set2.keySet());
        
        for (String key: intersection) {
            result += Math.min(set1.get(key), set2.get(key));
        }
        
        return result;
    }
    
    private int getUnionSize(Map<String, Integer> set1, Map<String, Integer> set2) {
        int result = 0;
        
        Set<String> union = new HashSet<>(set1.keySet());
        union.addAll(set2.keySet());
        
        for (String key: union) {
            if (set1.containsKey(key) && set2.containsKey(key)) {
                result += Math.max(set1.get(key), set2.get(key));
                continue;
            }
            
            if (set1.containsKey(key)) {
                result += set1.get(key);
                continue;
            }
            
            if (set2.containsKey(key)) {
                result += set2.get(key);
                continue;
            }
        }

        return result;
    }
    
    private Map<String, Integer> createMultiSet(String s) {
        Map<String, Integer> map = new HashMap<>();
        
        for (int i = 0; i < s.length() - 1; i++) {
            char ch1 = s.charAt(i);
            char ch2 = s.charAt(i + 1);
            if ('a' <= ch1 && ch1 <= 'z' &&
                'a' <= ch2 && ch2 <= 'z') {
                String key = "" + ch1 + ch2;
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
        }
        
        return map;
    }
}