프로그래머스 뉴스 클러스터링

뉴스 클러스터링 : programmers.co.kr/learn/courses/30/lessons/17677

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

이번 문제는 자카드 유사도를 가지고 푸는 문제 였다

자카드 유사도란 두 집합의 교집합 크기를 합집합 크기로 나눈값으로 해당값에 65536을 곱한 값을 구하는 문제였다.

참고로 공집합의 경우 1로 하여 구한다.

 

문제에서는 두개의 문자열을 주고 2개씩 끊어서 다중집합을 만든다 이때 공백문자나 특수문자는 지우고 영어쌍만 원소로 남는다.

먼저 나는 map에 두개씩 끊은 원소들을 저장하며 카운트를 세주었다.

그 뒤에 교집합은 map1과 map2중 작은 값을 택하고 합집합은 방대로 큰값을 택한뒤에 교집합을 합집합으로 나누어 주었다

import java.util.*;
class Solution {
	public Map<String, Integer> map1 = new HashMap();
	public Map<String, Integer> map2 = new HashMap();
	public Set<String> key = new HashSet<String>();

	public int solution(String str1, String str2) {
		// 교집합, 합집
		double min = 0, max = 0;
		str1 = str1.toLowerCase();
		str2 = str2.toLowerCase();

		StringBuilder sb = new StringBuilder();
		for (int i = 1; i < str1.length(); i++) {
			char c1 = str1.charAt(i - 1);
			char c2 = str1.charAt(i);

			if ('a' <= c1 && 'z' >= c1 && 'a' <= c2 && 'z' >= c2) {
				sb.append(c1).append(c2);
			} else {
				continue;
			}

			if (map1.get(sb.toString()) == null) {
				map1.put(sb.toString(), 1);
				key.add(sb.toString());
			} else {
				map1.put(sb.toString(), map1.get(sb.toString()) + 1);
			}
			sb.setLength(0);
		}

		for (int i = 1; i < str2.length(); i++) {
			char c1 = str2.charAt(i - 1);
			char c2 = str2.charAt(i);

			if ('a' <= c1 && 'z' >= c1 && 'a' <= c2 && 'z' >= c2) {
				sb.append(c1).append(c2);
			} else {
				continue;
			}

			if (map2.get(sb.toString()) == null) {
				map2.put(sb.toString(), 1);
				key.add(sb.toString());
			} else {
				map2.put(sb.toString(), map2.get(sb.toString()) + 1);
			}
			sb.setLength(0);
		}

		for (Iterator<String> iter = key.iterator(); iter.hasNext();) {
			String str = iter.next();
			if (map2.get(str) == null && map1.get(str) != null) {
				max += map1.get(str);
			} else if (map1.get(str) == null && map2.get(str) != null) {
				max += map2.get(str);
			} else {
				min += Math.min(map1.get(str), map2.get(str));
				max += Math.max(map1.get(str), map2.get(str));
			}
		}

		if (max == 0 && min == 0) {
			return 1 * 65536;
        }
		return (int) ((min / max) * 65536);
	}
}