[프로그래머스] level2. [1차] 뉴스 클러스터링 (자바 JAVA)

[ 문제 ]  [프로그래머스] level2. [1차] 뉴스 클러스터링 (자바 JAVA)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17677

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

---

# 접근 방법 및 풀이 

 

• 문제가 어렵진 않은데 제대로 읽었어야 하는 부분들이 있다. 
• " 특수문자가 들어가 있는 경우 그 글자 쌍을 버린다. " 라는 부분과 둘다 공집합일 경우 자카드 유사도 1인 부분이다.
• 난 처음에 문제를 또 대충 읽고, 특수문자는 그냥 replaceAll써서 처음부터 다 지워주고 시작했는데 문제는 쌍을 지워줘야한다.
• 먼저, 문제는 집합에 원소의 중복이 들어있는 경우 교집합과 합집합을 어떻게 나누냐가 핵심이다.
• 그러나 친절하게 문제에 나와있다. 교집합은 각 집합에서 중복되는 문자 갯수의 min, 합집합은 max다.
• 따라서 HashMap 두개를 사용해서 구현했다.
• str1은 map1, str2는 map2로 해당 문자열을 문자 2개씩 잘라서 해당 map에 넣는다.
• 이때 key는 '문자' value는 해당 문자의 갯수를 카운팅 해주면 된다.
• 그리고 각각의 map 전체를 보면서 교집합과 합집합을 구한다.
• map1에서 해당 key값이 map2에 있다면, 그때의 value를 비교하여 min과 max를 구해 교집합과 합집합에 각각 더한다.
• map1에서 해당 key값이 map2에 있다는 것은 교집합이라는 뜻이고, 이때 교집합값을 구했기 때문에 map2에서 해당 key값을 지워준다.
• map1에서 해당 key값이 map2에 없다면, 합집합 갯수에 더해주면 된다.
• map1에서 map1과 map2의 교집합의 갯수와 map1의 합집합 갯수를 세어줬으므로, map2의 key에 해당하는 value를 합집합에 더하면 된다.
• 자세한건 코드참조.

# 주의할 점 

 

• 특수문자가 들어가 있는 경우 그 글자 쌍을 버린다. 
• ab+c가 있을 경우, ab, b+, +c중에 ab만 남고 나머지 쌍은 버려짐.
• 둘다 공집합일 경우 자카드 유사도는 1이다.

 

JAVA 코드

import java.util.*;
class Solution {
	public static int solution(String str1, String str2) {
		int answer = 0;
		double union = 0; // 합
		double inter = 0; // 교
		HashMap<String, Integer> map1 = new HashMap<>();
		HashMap<String, Integer> map2 = new HashMap<>();
		str1 = str1.toUpperCase();
		str2 = str2.toUpperCase();
		for (int i = 0; i < str1.length() - 1; i++) {
			String s = str1.substring(i, i + 2).replaceAll("[^A-Z]", "");
			if(s.length() < 2)
				continue;
			map1.put(s, map1.getOrDefault(s, 0) + 1);
		}
		for (int i = 0; i < str2.length() - 1; i++) {
			String s = str2.substring(i, i + 2).replaceAll("[^A-Z]", "");
			if(s.length() < 2)
				continue;
			map2.put(s, map2.getOrDefault(s, 0) + 1);
		}

		if (map1.size() == 0 && map2.size() == 0)
			return 65536;

		for (String key : map1.keySet()) {
			if (map2.containsKey(key)) {
				inter += Math.min(map1.get(key), map2.get(key));
				union += Math.max(map1.get(key), map2.get(key));
				map2.remove(key);
			} else {
				union += map1.get(key);
			}
		}
		for (String key : map2.keySet()) {
			union += map2.get(key);
		}
		return (int) Math.floor((inter / union) * 65536);
	}
}

 

 

 

REVIEW