Programmers, [1차] 뉴스 클러스터링 : Java

자카드 유사도는 Double로 정의한다. 합집합이 0인 경우, 자카드 유사도는 1이 된다. 합집합이 0이 아닌 경우, 자카드 유사도는 교집합 크기 / 합집합 크기이다.

 

프로그래머스

 

처음에는

주어진 문자열을 charAt()으로 한 문자씩 떼어 영문자인지 확인하고,

영문자라면 Stringbuilder에 append하고,

다 했으면 toUpperCase()를 사용해 대문자로 통일하고 시작할까 ? 

생각했었다.

 

그런데 굳이 Stringbuilder로 새로운 문자열을 만들 필요가 없다.

기타 공백이나 숫자, 특수문자가 들어있는 경우는 그 글자 쌍을 버린다는 점을 놓쳐서 복잡하게 생각했다.

문제 풀이의 논리는 다음과 같다.

 

1) 주어진 문자열을 대문자(혹은 소문자)로 통일한다.

 

2) ArrayList로 다중집합 두 개(집합 A, 집합 B)를 만든다.

각 문자열마다 두 개의 문자를 떼어 둘 다 영문자인지 확인하고, 맞다면 다중집합에 넣는다.

 

3)  ArrayList로 두 다중집합의 합집합과 교집합을 만든다.

집합 B의 원소 중 집합 A의 원소와 동일한 원소가 있다면 해당 원소를 교집합 ArrayList에 넣는다. 모든 원소는 합집합 ArrayList에 넣는다.

 

4) 자카드 유사도를 구한다.

자카드 유사도는 Double로 정의한다.

합집합이 0인 경우, 자카드 유사도는 1이 된다. 합집합이 0이 아닌 경우, 자카드 유사도는 교집합 크기 / 합집합 크기이다.

 

5) answer은 자카드 유사도에 65536을 곱한 정수값이다.

 

 

 

다음은 문제 풀이 코드이다.

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        // 대문자로 통일한다.
        
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        
        // 다중집합 만들기
        
        ArrayList<String> multiSetA = new ArrayList<>();
        ArrayList<String> multiSetB = new ArrayList<>();
        
        for (int i=0; i<str1.length()-1; i++) {
            char first = str1.charAt(i);
            char second = str1.charAt(i+1);
            
            if (first >= 'A' && first <= 'Z' && second >= 'A' && second <= 'Z') {
                multiSetA.add(first + "" + second);
            }
        }
        
        for (int i=0; i<str2.length()-1; i++) {
            char first = str2.charAt(i);
            char second = str2.charAt(i+1);
            
            if (first >= 'A' && first <= 'Z' && second >= 'A' && second <= 'Z') {
                multiSetB.add(first + "" + second);
            }
        }
        
        Collections.sort(multiSetA);
        Collections.sort(multiSetB);
        
         // 합집합과 교집합 만들기
        
        ArrayList<String> union = new ArrayList<>();
        ArrayList<String> intersection = new ArrayList<>();
        
        for (String s : multiSetA) {
            if (multiSetB.remove(s)) {
                intersection.add(s);
            }
            union.add(s);
        }
        
        for (String s : multiSetB) {
            union.add(s);
        }
        
        // 자카드 유사도 구하기
        
        double jakard = 0;
        
        if (union.size() == 0) {
            jakard = 1;
        }
        else {
            jakard = (double)intersection.size() / (double)union.size();
        }
        
        answer = (int)(jakard * 65536);
        
        return answer;
    }
}