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

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

문제 이해하기

J(A,B) 에서 A,B 모두 0인 경우 → 1이다.

• 한 집합에서 원소가 중복되는 경우
  • {a,a,a,a,a}, {a,a,a} 인 경우 A교B , A합B → min(3,5) (즉, ,a,a,a ) max(3,5) (a,a,a,a,a)가 된다.
• 두 글자씩 끊어서 다중집합 만든다. : FRANCE → FR, RA, AN, NC, CE
  • 공백은 ? → 영문자로 된 글자 쌍만 유효하다. 공백이나 특수문자가 들어있는 경우 그 “글자 쌍!!” 을 버린다.
  • 대소문자 차이는 무시한다.

문제 풀기

• 먼저, 각 문자열을 두 글자씩 끊어서, 글자 쌍을 추출하는것이 필요

  • 그 두 글자중 알파벳이 아닌 것이 포함되면 → 버린다.
  • 그 외의 경우 → 그 두 글자를 대문자로 바꾸어서 → map 에다가 넣어두자.
    • 매번 서브 스트링을 생성해도 괜찮을까? → 문자열의 길이는 최대 1000 → 최대 약 999개의 문자열만 나옴 ㅇㅇ

• 그 결과 map1, map2 가 탄생한다.

• 교집합

  • map 1 을 순차적으로 돌면서 map 2 와 동일한 key 가 존재한다면 → 둘 중 최소 값을 sum 에 더한다.

• 합집합

  • map 1 을 순차적으로 돌면서 map 2와 동일한 키가 존재한다면 → 둘 중 max 값을 sum 에 더한다.

• 유사도 구하기

  • 0 ~ 1 사이의 실수 →

import java.util.*;

class Solution {
	public Map<String, Integer> map1 = new HashMap<>();
	public Map<String, Integer> map2 = new HashMap<>();

		public int solution(String str1, String str2) {
		int union = 0, inter = 0;

		extract(str1, map1);
		extract(str2, map2);

		inter = map1.entrySet()
			.stream()
			.map(e -> Integer.min(e.getValue(), map2.getOrDefault(e.getKey(), 0)))
			.reduce((a, b) -> a + b).orElseGet(()->0);

		union = map1.entrySet()
			.stream()
			.map(e -> Integer.max(e.getValue(), map2.getOrDefault(e.getKey(), 0)))
			.reduce((a, b) -> a + b).orElseGet(()->0);

		union += map2.entrySet()
			.stream()
			.filter(e -> map1.get(e.getKey()) == null)
			.map(e -> e.getValue())
			.reduce((a,b) -> a+b).orElseGet(()->0);
		
		if(union != 0) return (int)(inter/(double)union * 65536);
		else return 65536;
	}

	public void extract(String str, Map<String, Integer> map) {
		int len = str.length() - 1; // pair 를 만들어야 하기 때문
		String temp = null;

		str = str.toLowerCase();

		for (int idx = 0; idx < len; idx++) {
			if (!isAlpha(str.charAt(idx)))
				continue;
			if (!isAlpha(str.charAt(idx + 1)))
				continue;
			temp = str.substring(idx, idx + 2);
			map.put(temp, map.getOrDefault(temp, 0) + 1);
		}
	}

	public boolean isAlpha(char ch) {
		if (ch < 'a' || ch > 'z')
			return false;
		return true;
	}
}