[2018 카카오 블라인드] 뉴스 클러스터링 (JAVA)

문제

---

풀이

조건을 꼼꼼히 읽고 잘 맞춰 코드를 짜면 풀 수 있는 문제였다. 하지만 시간은 짱 많이 걸렸다..

1. 대소문자 구분 안 한다는 조건을 위해 알파벳은 모두 대문자로 변경해준다.
   • equalsIgnoreCase()를 사용해서 비교할 수도 있지만, HashMap에서 key를 저장할 때 같은 것으로 인식하게 하기 위해서는 애초에 하나로 통일하고 시작하는 것이 더 낫다.
2. jaccard()에서는 두 String의 subset을 구하고 이를 비교해서 similarity를 계산해낸다.
   • 마지막 리턴문에서 sumOfUnionCounts()를 그냥 union.size()로 하면 다중집합 케이스의 경우 제대로 계산이 되지 않는다.
3. getSubset()에서는 String의 subString을 차례로 탐색하며 알파벳으로만 이루어진 subString을 HashMap에 개수와 함께 저장하고 리턴한다.
   • 아주 예전에 알고리즘 문제 풀 때 알게 됐던 getOrDefault() 메소드가 바로 생각이 나서 적용할 수 있었다.
4. comapreSubsets()에서는 두 subset을 O(n^2)의 복잡도로 탐색하며 교집합과 합집합을 알아낸다.
   • 교집합: 두 key가 같은 경우, HashMap에서 불러온 두 값 중 작은 값으로 추가한다.
   • 합집합: 각각의 key에 대해 union의 value를 최대 카운트로 갱신한다.

---

코드

import java.util.*;

class Solution {
        
    private static final int CONST = 65536;

    private Map<String, Integer> union = new HashMap<>();
    private int intersectionCount;

    public int solution(String str1, String str2) {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        double similarity = jaccard(str1, str2);
        return (int) (similarity * CONST);
    }

    private double jaccard(String str1, String str2) {
        Map<String, Integer> subset1 = getSubset(str1);
        Map<String, Integer> subset2 = getSubset(str2);
        if (subset1.size() == 0 && subset2.size() == 0) return 1;
        compareSubsets(subset1, subset2);
        return (double) intersectionCount / sumOfUnionCounts();
    }
    
    private double sumOfUnionCounts() {
        return union.values().stream().mapToInt(Integer::valueOf).sum();
    }

    private Map<String, Integer> getSubset(String str) {
        Map<String, Integer> result = new HashMap<>();
        for (int i = 0; i < str.length() - 1; i++) {
            if (isAlphabet(str.charAt(i)) && isAlphabet(str.charAt(i + 1))) {
                String subString = str.substring(i, i + 2);
                result.put(subString, result.getOrDefault(subString, 0) + 1);
            }
        }
        return result;
    }

    private boolean isAlphabet(char ch) {
        return ch >= 'A' && ch <= 'Z';
    }

    private void compareSubsets(Map<String, Integer> subset1, Map<String, Integer> subset2) {
        for (String key1 : subset1.keySet()) {
            for (String key2 : subset2.keySet()) {
                if (key1.equals(key2)) {
                    intersectionCount += Math.min(subset1.get(key1), subset2.get(key2));
                    union.put(key1, Math.max(subset1.get(key1), subset2.get(key2)));
                } else {
                    union.put(key1, Math.max(subset1.get(key1), union.getOrDefault(key1, 0)));
                    union.put(key2, Math.max(subset2.get(key2), union.getOrDefault(key2, 0)));
                }
            }
        }
    }
}