[Java] 프로그래머스 / [1차] 뉴스 클러스터링

[1차] 뉴스 클러스터링

문제

---

문제 설명

두 문자열의 유사도를 구하는 문제이다.

자카드 유사도라는 것을 구하는데 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값이다.

만약 두 집합이 모두 공집합이라면 자카드 유사도는 1이며, 문제에서는 입력으로 들어온 문자열을 두 글자씩 끊어서 다중집합의 원소로 보고, 이렇게 만들어진 두 집합의 유사도를 구하는 문제이다.

---

구현

일단 집합을 만들기 위해서 HashMap을 사용했다. 교집합, 합집합의 크기를 구해야하기때문에 String, Integer 를 가지는 HashMap을 사용했다.

문자열을 두개씩 가져와서 유효성 검사를 해주고 map에 넣어준다.

for(int i = 0; i < str1.length() - 1; i++){
	char a = str1.charAt(i);
	char b = str1.charAt(i + 1);
	if(a >= 'a' && a <= 'z' && b >= 'a' && b <= 'z'){
		String pair = "" + a + b;
		map1.put(pair, map1.getOrDefault(pair, 0) + 1);
	}
}

이렇게 만들어진 배열들로 교집합과 합집합을 구해야 한다.

일단은 HashSet 에 모든 값들을 넣어준다.

Set<String> keys = new HashSet<>();
keys.addAll(map1.keySet());
keys.addAll(map2.keySet());

이렇게 생성된 HashSet 내의 각 key 값에 대해서 위에서 만든 집합이 각각 몇개씩을 가지고 있는지 확인한다.

교집합은 둘 중 적은 개수가 들어가고, 합집합은 둘 중 많은 개수가 들어간다.

예를 들어 "ab" 라는 문자열이 map1에는 2개, map2에는 3개가 있다고 했을 때, 교집합의 크기는 적은쪽인 map1의 2개, 합집합의 크기는 많은쪽인 map2의 3개가 된다.

---

코드

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        
        //표준화
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        
        //배열 만들기 (str1)
        for(int i = 0; i < str1.length() - 1; i++){
            char a = str1.charAt(i);
            char b = str1.charAt(i + 1);
            if(a >= 'a' && a <= 'z' && b >= 'a' && b <= 'z'){
                String pair = "" + a + b;
                map1.put(pair, map1.getOrDefault(pair, 0) + 1);
            }
        }


        //배열 만들기 (str2)
        for(int i = 0; i < str2.length() - 1; i++){
            char a = str2.charAt(i);
            char b = str2.charAt(i + 1);
            if(a >= 'a' && a <= 'z' && b >= 'a' && b <= 'z'){
                String pair = "" + a + b;
                map2.put(pair, map2.getOrDefault(pair, 0) + 1);
            }
        }
        
        
        int intersection = 0;
        int union = 0;
        
        Set<String> keys = new HashSet<>();
        keys.addAll(map1.keySet());
        keys.addAll(map2.keySet());
        
        for(String key : keys) {
            int cnt1 = map1.getOrDefault(key, 0);
            int cnt2 = map2.getOrDefault(key, 0);
            intersection += Math.min(cnt1, cnt2);
            union += Math.max(cnt1, cnt2);
        }
        
        
        if(union == 0) return 65536;
        else return (int)((double) intersection / union * 65536);
    }
}