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

문제 설명

 

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

 

접근 방법

해당 문제는 두 개의 문자열이 주어졌을 때 이들간 자카드 유사도를 요구하고있습니다.

 

우선은 문제에서 요구하는 방식대로 각각의 문자열에 대해 다중집합 원소를 구하는 로직을 작성했습니다.

    private Map<String, Integer> getMultipleSets(String str) {
        Map<String, Integer> multipleSets = new HashMap<>();
        Pattern p = Pattern.compile("[^a-zA-Z]");
        String key;
        for (int i = 0; i < str.length() - 1; i++) {
            key = str.substring(i, i + 2);
            if (!p.matcher(key).find()) {
                multipleSets.put(key, multipleSets.getOrDefault(key, 0) + 1);
            }
        }

        return multipleSets;
    }

 

이때, 알파벳이 아닌 특수문자 등을 포함하고 있는 원소의 경우는 제외해야하므로, 정규 표현식을 통해 알파벳만 포함하는 경우를 검증한 후 이를 원소로 담았습니다.

 

여기서 HashMap을 쓴 이유는 자카드 유사도를 구하기 위함이었는데, 자카드 유사도의 경우 교집합의 원소를 구할 때, 부분집합간 중복되는 원소가 있다면 각 부분집합이 가지고 있는 해당 원소의 개수가 더 적은 것을 교집합의 원소로 갖기 때문입니다.

 

        int intersectionCount = 0;
        for (String key : set1.keySet()) {
            if (set1.containsKey(key) && set2.containsKey(key)) {
                intersectionCount += Math.min(set1.get(key), set2.get(key));
            }
        }

 

또한 합집합의 원소를 구할 때도 특이하게 중복되는 원소가 있다면 각 부분집합이 가지고 있는 해당 원소의 개수가 더 많은 것을 합집합의 원소로 갖습니다.

 

        int unionCount = 0;
        for (String key : set1.keySet()) {
            if (set2.containsKey(key)) {
                unionCount += Math.max(set1.get(key), set2.get(key));
                set2.remove(key);
            } else {
                unionCount += set1.get(key);
            }
        }

        for (String key : set2.keySet()) {
            unionCount += set2.get(key);
        }

 

 

전체 소스 코드

import java.util.HashMap;
import java.util.Map;
import java.util.regex.Pattern;

class Solution {

    public int solution(String str1, String str2) {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        Map<String, Integer> set1 = getMultipleSets(str1);
        Map<String, Integer> set2 = getMultipleSets(str2);
        if (set1.size() == 0 && set2.size() == 0) {
            return 65536;
        }

        int intersectionCount = 0;
        for (String key : set1.keySet()) {
            if (set1.containsKey(key) && set2.containsKey(key)) {
                intersectionCount += Math.min(set1.get(key), set2.get(key));
            }
        }

        int unionCount = 0;
        for (String key : set1.keySet()) {
            if (set2.containsKey(key)) {
                unionCount += Math.max(set1.get(key), set2.get(key));
                set2.remove(key);
            } else {
                unionCount += set1.get(key);
            }
        }

        for (String key : set2.keySet()) {
            unionCount += set2.get(key);
        }

        return (int) Math.floor(( (double) intersectionCount / unionCount) * 65536);
    }

    private Map<String, Integer> getMultipleSets(String str) {
        Map<String, Integer> multipleSets = new HashMap<>();
        Pattern p = Pattern.compile("[^a-zA-Z]");
        String key;
        for (int i = 0; i < str.length() - 1; i++) {
            key = str.substring(i, i + 2);
            if (!p.matcher(key).find()) {
                multipleSets.put(key, multipleSets.getOrDefault(key, 0) + 1);
            }
        }

        return multipleSets;
    }
}

 

 

참고자료

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