[프로그래머스] 뉴스 클러스팅 (Lv2/2018 KAKAO BLIND RECRUITMENT)

문제

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

---

고민1. 문자열 다중 집합 추출

• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

String.substring()을 활용하여 문자열을 두 글자씩 끊는다.
또한 두 가지 조건은

• 영문자로 된 글자 쌍만 유효하다
  -> String.matches()로 영문자로만 이루어져있는지 검사한다.
• 대소문자는 구분하지 않는다
  -> String.toUpperCase() 또는 String.toLowerCase()로 전체 대문자, 전체 소문자로 변경한다.

class Solution {
    String match="^[a-zA-Z]*$"; 
    
    // 문자열 다중집합 추출 메소드
    public void getStrSet(String str, ArrayList<String> strList){    
        String temp="";
        for(int i=0; i<str.length()-1;i++){
            temp= str.substring(i,i+2);
            if(temp.matches(match))
                strList.add(temp);
        } 
    }
    
    public int solution(String str1, String str2) {
        double answer = 65536.0;
        ArrayList<String> str1List, str2List =new ArrayList<String>();
        
        getStrSet(str1.toUpperCase(), str1List);
        getStrSet(str2.toUpperCase(), str2List);
        
        return answer;
    }
}

고민2. 자카드 유사도 - 교집합과 합집합 구하기

자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

고려해야할 점은 집합이 다중집합이라는 것이다!
다중 집합의 자카드 유사도는 아래 예시와 같이 구해야 한다.

다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면,
교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로,
자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.

일반적인 set을 이용한 교집합, 합집합 구하기는 단일 집합일 때만 구할 수 있다.
때문에 직접 구현해주어야 함...

집합의 벤 다이어그램을 보면

1. 차집합 A-B 값을 A에서 빼면 A,B의 교집합이다.
2. A,B의 합집합은 A-B ,B-A , 교집합을 다 더한 값이라고 할 수 있다.

Array.remove()와 Array.addAll()을 이용하여 메소드를 작성했다.

// 자카드 유사도 메소드
    public double Jac(ArrayList<String> A, ArrayList<String> B){
        ArrayList<String> AsubB=(ArrayList<String>)A.clone();
        ArrayList<String> BsubA=(ArrayList<String>)B.clone();
        ArrayList<String> intersection=(ArrayList<String>)A.clone();
        ArrayList<String> union=new ArrayList<String>();

        if(A.size()==0 && B.size()==0)
            return 1.0;
        else{
             // A-B
            for(String s:B){   
                AsubB.remove(s);
            }

            // B-A
            for(String s:A){    
                BsubA.remove(s);
            }

            // 교집합
            for(String s:AsubB){  
                intersection.remove(s);
            }

            // 합집합
            union.addAll(AsubB);
            union.addAll(BsubA);
            union.addAll(intersection);
        }

        return (double)intersection.size()/union.size();
    }

---

집합의 원리를 이용하여 정답을 맞추긴 했는데...
그냥 어떻게든 굴러가는 코드를 짠 느낌이다...

---

최종코드

GitHub Java-algorithm-practice/프로그래머스/lv2/17677. ［1차］ 뉴스 클러스터링/

import java.util.*;

class Solution {
    public static String match="^[a-zA-Z]*$"; 
    
    // 문자열 다중집합 추출 메소드
    public void getStrSet(String str, ArrayList<String> strList){    
        String temp="";
        for(int i=0; i<str.length()-1;i++){
            temp= str.substring(i,i+2);
            if(temp.matches(match))
                strList.add(temp);
        } 
    }
    
    // 자카드 유사도 메소드
    public double Jac(ArrayList<String> A, ArrayList<String> B){
        ArrayList<String> AsubB=(ArrayList<String>)A.clone();
        ArrayList<String> BsubA=(ArrayList<String>)B.clone();
        ArrayList<String> intersection=(ArrayList<String>)A.clone();
        ArrayList<String> union=new ArrayList<String>();
        
        if(A.size()==0 && B.size()==0)
            return 1.0;
        else{
             // A-B
            for(String s:B){   
                AsubB.remove(s);
            }
            
            // B-A
            for(String s:A){    
                BsubA.remove(s);
            }
            
            // 교집합
            for(String s:AsubB){  
                intersection.remove(s);
            }

            // 합집합
            union.addAll(AsubB);
            union.addAll(BsubA);
            union.addAll(intersection);
        }
        
        return (double)intersection.size()/union.size();
    }
    public int solution(String str1, String str2) {
        int answer = 65536;
        ArrayList<String> str1List=new ArrayList<String>(), str2List =new ArrayList<String>();
        
        getStrSet(str1.toUpperCase(), str1List);
        getStrSet(str2.toUpperCase(), str2List);
        
        answer*=Jac(str1List,str2List);
        
        return (int)(Math.floor(answer));
    }
}