[알고리즘] 프로그래머스 뉴스 클러스터링

- 문제

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

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

- 코드 설명

처음 문제를 풀기 시작했을 때 HashMap을 사용하여 풀면 간단하다고 생각했으나 이것은 확장된 자카드 유사도가 아닌것을 알았고 ArrayList로 변환 후 교집합을 구하기 위해 각각의 ArrayList를 정렬했습니다.

 

집합의 원소는 정규식을 사용하여 구했습니다.

 

 

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        ArrayList<String> set1 = new ArrayList<>();
        ArrayList<String> set2 = new ArrayList<>();
        
        makeSet(str1, set1);
        makeSet(str2, set2);
        
        if(set1.size() + set2.size() == 0) return 65536;
        
        Collections.sort(set1);
        Collections.sort(set2);
        
        answer = (int)(makeJ(set1,set2) * 65536);
        return answer;
    }
    
   
    private double makeJ(ArrayList<String> set1 , ArrayList<String> set2){
        int countUnion = 0;
        int countIntersection = 0;
        int idx = 0, len1, len2;
        
        len1 = set1.size();
        len2 = set2.size();
        
        for(int i=0; i<len1; i++){
            for(int j=idx; j<len2; j++){
                if(set1.get(i).equals(set2.get(j)) == true) {
                    countIntersection++;
                    idx = j+1;
                    break;
                }
            }
        }
        countUnion = set1.size() + set2.size() - countIntersection;
        return countIntersection/(double)countUnion;
    }
    
    private void makeSet(String str , ArrayList<String> set){
        int len = str.length();
        for(int i=0; i<len-1; i++){
            String temp = str.substring(i,i+2);
            if(temp.matches("^[a-zA-Z]*$")){
                temp = temp.toUpperCase();
                set.add(temp);
            }
        }
    }
}

 

- 결과