2018 - [1차] 뉴스 클러스터링

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

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

[ 문제풀이 ]

문자열의 최대 길이가 1000이기 때문에 모든 경우의 수를 다 구하여 교집합과 합집합을 구해주면 해결할 수 있다.

​먼저 대문자, 소문자를 구분하지 않기 때문에 대문자나 소문자로 통일하자.

​나는 다중집합의 수를 관리하기 위해 HashMap을 사용하였다. 각 문자열을 돌면서 만들 수 있는 원소 중 영문자로만 이루어져 있는 경우 HashMap에 넣어주면서 개수를 갱신하였다.

​두 문자열 각각 다중집합을 구성하였다면 한 문자열의 HashMap을 돌면서 교집합과 합집합을 구해주면 된다. 주의해야 할 점은 교집합, 합집합이 0인 경우 65536을 반환해야 한다.

import java.util.*;

class Solution {
	public int solution(String str1, String str2) {
        //대문자로 통일
		str1 = str1.toUpperCase();
		str2 = str2.toUpperCase();

		HashMap<String, Integer> hm_str1 = new HashMap<>();
		HashMap<String, Integer> hm_str2 = new HashMap<>();

		int all_Count = 0; //전체 집합

		for (int i = 0; i < str1.length() - 1; ++i) {
            //영문자가 아니면 패스
            if (!Character.isAlphabetic(str1.charAt(i)) || !Character.isAlphabetic(str1.charAt(i + 1)))
                continue;
            
			String str = str1.substring(i, i + 2);
			all_Count++;
            
			if (hm_str1.containsKey(str)) {
				hm_str1.replace(str, hm_str1.get(str) + 1);
			} else {
				hm_str1.put(str, 1);
			}
		}

		for (int i = 0; i < str2.length() - 1; ++i) {
            //영문자가 아니면 패스
		    if (!Character.isAlphabetic(str2.charAt(i)) || !Character.isAlphabetic(str2.charAt(i + 1)))
                continue;
            
            String str = str2.substring(i, i + 2);
			all_Count++;

			if (hm_str2.containsKey(str)) {
				hm_str2.replace(str, hm_str2.get(str) + 1);
			} else {
				hm_str2.put(str, 1);
			}
		}

		Iterator<String> it = hm_str1.keySet().iterator();
        double intersection = 0;
        
        //hm_str1의 원소들을 돌면서
		while (it.hasNext()) {
			String str = it.next();
            
            //hm_str2가 가지고 있는 원소라면 작은 값을 교집합에 더해줌
			if (hm_str2.containsKey(str)) {
				intersection += Math.min(hm_str1.get(str), hm_str2.get(str));
			}
		}

        //합집합 = 전체 집합 - 교집합
		double union = all_Count - intersection;
        
        //둘다 공집합인 경우
        if (intersection == 0 && union == 0) return 65536;
		
        double jacquard = intersection / union;
		return (int)(jacquard * 65536);
	}
}