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

문제

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

프로그래머스

"자카드 유사도"는 두 집합 간의 유사도를 검사하는 방법 중 하나로, 두 집합 `A`와 `B` 사이의 자카드 유사도는 두 집합의 교집합의 크기를 두 집합의 합집합의 크기로 나눈 값이다.

문제에서는 자카드 유사도를 원소의 중복을 허용하는 집합인 다중집합에 대해서 확장하고 있다.

두 문자열이 주어지면, 이 문자열을 두 문자씩 끊어서 다중집합을 만들어 두 문자열 간의 자카드 유사도를 계산한다.

이때, 대문자와 소문자를 구별하지 않으며(`AB`와 `Ab`는 같은 원소로 취급), 공백이나 특수문자가 포함된 원소는 제외한다.

 

풀이

우선 문자열을 다중집합으로 변환해야 한다. 이때 주의할 점은 대소문자를 구분하지 않으며, 공백이나 특수 문자가 포함되면 원소에서 제외해야 한다는 것이다. 일단 모두 소문자로 변환한 뒤, 공백과 특수 문자를 제외해주려고 했다.

 

이때 영어 소문자가 아닌 경우를 아스키코드를 통해 계산하고자 했으나, 소문자가 몇부터 시작하는지 기억이 나질 않아 찾아볼 수 밖에 없었다. (굳이 숫자로 하지 않고 `'a'`이런 식으로 계산하면 된다는 것을 늦게 알았다.)

• A ~ Z: 65 ~ 90
• a ~ z : 97 ~ 122

두 문자열을 다중집합으로 변환한 뒤 교집합과 합집합을 계산하고자 List를 사용했는데, 유사도를 계산하는데 필요한 건 교집합의 원소의 개수와 합집합 원소의 개수이므로 집합에 대한 정보를 굳이 유지하고 있을 필요는 없다는 것을 알았다. 앞으로는 문제를 잘 파악해서 굳이 유지할 필요없는 데이터는 저장하지 않도록 해야할 것 같다.

 

교집합은 두 번째 다중집합의 원소가 첫 번째 다중집합에 포함되어 있으면 제거하여 구했다.

합집합은 두 번째 다중집합에서 교집합을 제거한 뒤, 첫 번째 다중집합에 더하는 식으로 구했다.

 

코드

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        List<String> multipleSet1 = getMultipleSet(str1);
        List<String> multipleSet2 = getMultipleSet(str2);

        // 교집합 생성
        List<String> intersection = new ArrayList<>();
        List<String> copySet1 = new ArrayList<>(multipleSet1);
        for (String element : multipleSet2) {
            if (copySet1.contains(element)) {
                intersection.add(element);
                copySet1.remove(element);
            }
        }
        
        // 합집합 생성 (다중 집합 1 + 다중 집합 2 - 교집합)
        List<String> union = new ArrayList<>(multipleSet1);
        List<String> copySet2 = new ArrayList<>(multipleSet2);
        for (String element : intersection) {
            copySet2.remove(element);
        }
        union.addAll(copySet2);
    
        if (union.size() == 0) return 65536;
        double similarity = ((double) intersection.size() / union.size()) * 65536;
        
        return (int) similarity;
    }
    
    public static List<String> getMultipleSet(String str) {
        List<String> multipleSet = new ArrayList<>();
        for (int i = 0; i < str.length() - 1; i++) {
            String current = str.substring(i, i+2).toLowerCase();
            if (current.charAt(0) < 'a' || current.charAt(0) > 'z' ||
                current.charAt(1) < 'a' || current.charAt(1) > 'z') {
                continue;
            }
            multipleSet.add(current);
        }
        return multipleSet;
    }
}