Level2 - [1차] 뉴스 클러스터링 (2018 KAKAO BLIND RECRUITMENT)

문제를 이해하는데 많은 시간이 걸린 문제.

 

"FRANCE"와 "FRENCH"가 주어졌을 때,

이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며,

교집합은 {FR, NC},

합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로,

두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.

교집합은 2 , 합집합은 8 

0.25 * 65536 을 리턴하면 되는 문제

 

 

문제 핵심 ( 문자열을 2개의 문자들로 나눠라, 교집합, 합집합 구해라)

 

 

1. 문자 추출 : 슬라이딩 윈도우

문자열에서 길이 2만큼의 문자열들로 추출하여 리스트로 만드는 작업 진행

문자열 마다 2개의 문자들로 묶는 작업 ( 2개의 문자중 알파벳이 아니면 추가하지 않는다.)

 

2. 교집합 구하기

 문자리스트에서 다른 문자리스트가 있으면 카운트 하고 다른 문자리스트에서 그 값을 제거

 

3. 합집합 구하기

 전체수에서 교집합 빼주기

 

public static int solution(String str1, String str2) {
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();

        ArrayList<String> arr1 = new ArrayList<>();
        ArrayList<String> arr2 = new ArrayList<>();
        // 1. 문자 추출 : 슬라이딩 윈도우
        int lt=0;
        for(int rt=2; rt<=str1.length(); rt++){
            String str = str1.substring(lt++, rt);
            if(!Character.isAlphabetic(str.charAt(0)) || !Character.isAlphabetic(str.charAt(1)) ) continue;
            arr1.add(str);
        }
         lt=0;
        for(int rt=2; rt<=str2.length(); rt++){
            String str = str2.substring(lt++, rt);
            if(!Character.isAlphabetic(str.charAt(0)) || !Character.isAlphabetic(str.charAt(1)) ) continue;
            arr2.add(str);
        }


        int cnt = 0;
        int size = arr2.size();
        // 2. 교집합 구하기
        for(String x : arr1){
            if(arr2.contains(x)) {
                cnt++;
                arr2.remove(x);
            }
        }
        // 3. 합집합
        double sum = arr1.size()+size;
        if(sum-cnt==0) return 65536;
        double result = (cnt/(sum-cnt))*65536;
        int a = (int) Math.floor(result);
        return a;

    }