[Programmers]LV2 - 뉴스 클러스터링

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

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

 

 

 

문제 파악

 

교집합, 합집합을 만들 수 있는가?라고 생각하고 접근하였다.

 

1. 각 문자열 Str1과 Str2에서 2 글자씩 끊어서 집합의 원소를 만든다.

(단, 2글자 모두 영문자이어야 하며 , 특수문자, 숫자가 들어갈 시에는 원소가 되지 못한다.)

2. 문자열 Str1가 "AAA" 라면 집합 A의 원소는 "AA", "AA"로 2개가 만들어진다 ( 중복 허용 )

3. 영문자의 대소문자는 따지지 않는다.

4. 예제 "E=M*C^2"에서 따져보면 교집합, 합집합 모두 공집합이므로 0 나누기 오류가 발생하니 1로 처리하여 65536을 곱한다라고 추측했다. 결론은 맞게 됐지만

 

문제를 해결하기 위해서 HashMap<String,Integer>를 사용하였다.

( 중복된 데이터를 늘려나갈것이 아니라 Value로써 관리하려고 )

 

import java.util.*;
class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        double multi  = 65536;
        
        HashMap<String,Integer> ha = new HashMap<>();
        HashMap<String,Integer> hb = new HashMap<>();
        
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        
        ha = MakeElments(str1);
        hb = MakeElments(str2);
        
        double inter = 0;
        double union = 0;
        
        //교집합 구하기
        for(String key : ha.keySet())
        {                        
            if(hb.containsKey(key)){
                inter+= Math.min(ha.get(key),hb.get(key));
            }
        }
        
        // 합집합 계산 : A집합의 갯수 + B집합의 갯수 - 교집합의 갯수
        union+= UnionCnt(ha) + UnionCnt(hb) - inter;
        
        // 합집합이 0이하 이면 1로 계산 처리 나누기 오류 때문에
        if(union <= 0){
            answer = (int)multi;
        }
        else
        {
            double jacquard = inter/union * multi;
            answer = (int)jacquard;            
        }        
        return answer;
    }
    
    public HashMap<String,Integer> MakeElments(String str)
    {
        HashMap<String,Integer> hs  = new HashMap<>();
        for(int idx = 0; idx<str.length()-1;idx++)
        {
            char cur = str.charAt(idx);
            char next = str.charAt(idx+1);
            if('A' <= cur && cur <='Z' && 'A'<= next && next <='Z'){
                String s = Character.toString(cur)+Character.toString(next);                
                hs.put(s,hs.getOrDefault(s,0)+1);
            }
        }
        return hs;
    }
    public int UnionCnt(HashMap<String,Integer> hs)
    {
        int cnt = 0;
        for(String key : hs.keySet())
        {
            cnt+= hs.get(key);
        }
        return cnt;
    }
}