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

코드 힌트

1. 소문자 변환
   • 입력된 두 문자열을 모두 소문자로 변환하여 대소문자 구분 없이 비교할 수 있도록 합니다.
2. 다중집합 생성
   • 문자열을 2글자씩 잘라서 다중집합을 만듭니다.
   • 각 부분 문자열은 알파벳으로만 구성되어야 하며, 두 개의 문자로 구성된 경우에만 다중집합에 추가됩니다.
   • 예를 들어, "ab+c"라는 문자열이 있을 때, "ab"는 다중집합에 포함될 수 있지만 "b+"와 "+c"는 알파벳이 아니므로 다중집합에 포함되지 않습니다.
   • 이 다중집합들은 나중에 교집합과 합집합을 계산하는 데 사용됩니다.
3. 자카드 유사도 계산
   • str1과 str2의 다중집합이 모두 비어 있을 때, 두 문자열은 완전히 유사하다고 간주하므로 유사도는 1로 간주되어 65536을 반환합니다.
   • 교집합과 합집합의 크기를 구한 후, 교집합 크기를 합집합 크기로 나누어 자카드 유사도를 계산합니다.
   • 자카드 유사도는 두 문자열 간의 유사도를 나타내는 지표로, 최종적으로 이 값을 65536을 곱하여 정수로 반환합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        // 소문자로 변환
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        
        // str1과 str2의 다중집합을 저장할 리스트 생성
        List<String> list1 = new ArrayList<>();
        List<String> list2 = new ArrayList<>();
        multipleSets(list1, str1); // str1의 다중집합 생성
        multipleSets(list2, str2); // str2의 다중집합 생성
        
        // 교집합과 합집합 크기를 저장할 변수 선언 (소수점 계산을 위해 double 타입 사용)
        double union = 0.0;
        double intersection = 0.0;
        
        // 자카드 유사도 계산
        if (list1.size() == 0 && list2.size() == 0) {
            // 두 문자열이 모두 공백이면 유사도는 1이므로 65536 반환
            return 65536;
        }
        
        // list1의 각 요소에 대해 처리
        for (int i = 0; i < list1.size(); i++) {
            String str = list1.get(i);
            
            // 교집합 계산: list2에 해당 요소가 있으면 교집합 크기 증가
            if (list2.contains(str)) {
                intersection++;
                list2.remove(str); // 중복 방지를 위해 list2에서 해당 요소 제거
            }
            union++; // 합집합 크기 증가
        }
        
        // union + list2.size() 계산: list1에 포함되지 않은 list2의 요소들 합집합에 추가
        return (int) (intersection / (union + list2.size()) * 65536);
    }
    
    // 다중집합을 생성하는 메서드
    static void multipleSets(List<String> list, String str) {
        for (int i = 0; i < str.length() - 1; i++) {
            // 문자열에서 2글자씩 잘라서 알파벳이 아닌 부분은 제거
            String s = str.substring(i, i + 2).replaceAll("[^a-zA-Z]", "");
            // 2글자로 이루어진 경우에만 리스트에 추가
            if (s.length() == 2)
                list.add(s);
        }
    }
}