[ 프로그래머스 ] 17677 뉴스 클러스터링

📌 Problem

두 개의 문자열이 주어졌을 때 자카드 유사도를 구한 값에 65536를 곱한 정수 부분을 반환하면 된다. 이때 자카드 유사도로 사용할 원소는 문자열을 2개의 문자씩 끊은 것이다. 알파벳 이외의 문자가 있는 원소는 제외하며 대소문자는 구별하지 않는다. 자카드 유사도는 교집합 개수 / 합집합 개수이며 합집합이 없을 경우 1이 된다.

📌 Solution

Map<String, Integer> 자료구조를 사용하여 간단하게 구할 수 있다. String은 문자열의 2 길의 부분 문자열이면 Integer은 해당 부분 문자열의 개수이다. 각 문자열에 대한 map을 생성할 후 교집합의 개수와 합집합의 개수를 구한다.

• 교집합
  두 문자열 집합에 모두 포함된 원소 중에서 더 적은 값을 더한다. 예를 들어 두 문자열 집합에 문자열 "AB"가 있는데 하나는 2개를 또 다른 하나는 4개를 가지면 2개를 교집합 개수에 더한다.

• 합집합
  두 문자열 집합에 모두 포함된 원소와 하나에만 포함된 원소를 다르게 계산한다. 모두 포함된 원소의 경우 더 많은 개수를 가진 값을 합집합 개수에 더한다. 교집합과 같은 예시를 생각하면 4를 합집합 개수에 더한다. 한 쪽에만 있는 경우에는 해당 값을 합집합 개수에 더한다.

📌 Code

public int solution(String stringA, String stringB) {
    StringJaccard jaccard = new StringJaccard(stringA, stringB);
    return (int) (jaccard.similarity() * 65536);
}

class StringJaccard {

    private final Map<String, Integer> setA, setB;

    public StringJaccard(String stringA, String stringB) {
        setA = createSet(stringA);
        setB = createSet(stringB);
    }

    public double similarity() {
        double same = 0, sum = 0;

        for (Map.Entry<String, Integer> entry : setA.entrySet()) {
            if (setB.containsKey(entry.getKey())) {
                same += Math.min(entry.getValue(), setB.get(entry.getKey()));
            }
            sum += Math.max(entry.getValue(), setB.getOrDefault(entry.getKey(), 0));
        }

        for (Map.Entry<String, Integer> entry : setB.entrySet()) {
            if (!setA.containsKey(entry.getKey())) {
                sum += entry.getValue();
            }
        }

        return sum == 0 ? 1 : same / sum;
    }

    private Map<String, Integer> createSet(String string) {
        Map<String, Integer> set = new HashMap<>();
        for (int i = 0; i < string.length() - 1; i++) {
            String substring = string.substring(i, i + 2);
            if (substring.matches("[A-Za-z][A-Za-z]")) {
                set.merge(substring.toUpperCase(), 1, Integer::sum);
            }
        }
        return set;
    }
}