뉴스 클러스터링

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

프로그래머스

 

크게 두가지를 신경써야 한다.

1. 주어진 문자열을 두글자씩 끊어 다중집합의 원소로 만들되, 알파벳을 제외한 특수문자가 포함된 원소는 제외시켜야 함.

(특수문자를 미리 제거하고 문자열을 두글자씩 끊게 되면 잘못된 원소가 집합에 포함되므로 주의. 예를들어 a+b 일때 ab라는 원소가 포함되어버림)

 

2. 이렇게 만들어진 두개의 다중집합을 비교하여 교집합 구하기. 합집합은 두 집합을 더하고, 교집합을 한번만 빼주면 합집합이 된다.

 

 

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        
        str1 = str1.toLowerCase().replaceAll("[^a-zA-Z]", " ");
        str2 = str2.toLowerCase().replaceAll("[^a-zA-Z]", " ");
        
        List<String> list1 = new ArrayList();
        List<String> list2 = new ArrayList();
        
        // 집합 만들기
        for (int i = 0; i < str1.length() - 1; i++) {
            
            String str = str1.substring(i, i+2);
            if (str.indexOf(" ") >= 0) continue;
            
            list1.add(str);
        }
        
        for (int i = 0; i < str2.length() - 1; i++) {
            
            String str = str2.substring(i, i+2);
            if (str.indexOf(" ") >= 0) continue;
            
            list2.add(str);
        }
        
        // 교집합(dup) 구하기
        int dup = 0;
        for (String str : list1) {
            
            for (int i = 0; i < list2.size(); i++) {
                
                String find = list2.get(i);
                if (str.equals(find)) {
                    dup++;
                    list2.remove(i);
                    break;
                }
                
            }
            
        }
        
        int size1 = list1.size();
        int size2 = list2.size() + dup;
        
        if (size1 == dup && size2 == dup) return 65536;
        
        double ans = 1.0 * dup / (size1 + size2 - dup);
        
        return (int) (ans * 65536.0);
        
    }
    
}