[programmers] 뉴스 클러스터링 - Java

뉴스 클러스터링

문제 설명

• 카카오 첫 공채..'블라인드' 방식 채용

• 카카오, 합병 후 첫 공채.. 블라인드 전형으로 개발자 채용

• 카카오, 블라인드 전형으로 신입 개발자 공채

• 카카오 공채, 신입 개발자 코딩 능력만 본다

• 카카오, 신입 공채.. "코딩 실력만 본다"

• 카카오 "코딩 능력만으로 2018 신입 개발자 뽑는다"

입력 형식

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.

• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.

• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

출력 형식

예제 입출력

solution.java

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(String str1, String str2) {
        Map<String, Integer> map1 = generateMultiset(str1.toLowerCase());
        Map<String, Integer> map2 = generateMultiset(str2.toLowerCase());

        if (map1.isEmpty() && map2.isEmpty()) {
            return 65536;
        }

        double intersection = 0.0;
        double union = 0.0;

        for (Map.Entry<String, Integer> entry : map1.entrySet()) {
            String key = entry.getKey();
            int count1 = entry.getValue();
            int count2 = map2.getOrDefault(key, 0);
            intersection += Math.min(count1, count2);
            union += Math.max(count1, count2);
        }

        for (Map.Entry<String, Integer> entry : map2.entrySet()) {
            String key = entry.getKey();
            if (!map1.containsKey(key)) {
                union += entry.getValue();
            }
        }

        double similarity = intersection / union;
        return (int) (similarity * 65536);
    }

    private Map<String, Integer> generateMultiset(String str) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < str.length() - 1; i++) {
            String pair = str.substring(i, i + 2);
            if (pair.matches("[a-z]{2}")) {
                map.put(pair, map.getOrDefault(pair, 0) + 1);
            }
        }
        return map;
    }
}

핵심 키워드

• generateMultiset() 메서드는 입력받은 문자열을 반복하며 substring()을 통해 문자 쌍을 추출한다.
• 그 후 만든 문자 쌍이 영문 소문자로만 이루어져 있는지 정규식을 통해 확인한다.
• 만약 정규식에 해당한다면 map에 값을 추가하고, 이미 존재하는 경우 value를 1 증가시킨다.

• generateMultiset() 메서드를 통해 만든 두 다중 집합이 비어있다면 65536을 리턴한다.

• 그 후 첫 번째 다중 집합을 반복한다.
• 각 항목에 대해 key와 value를 가져오고, 만약 두 번째 다중집합이 첫 번째 다중집합의 key를 가지고 있다면, 해당 value와 첫 번째 다중 집합의 value를 비교해서 최소 개수를 교집합의 값에 더한다.
• 그 후 해당 value와 첫 번째 다중 집합의 value를 비교해서 최대 개수를 합집합의 값에 더한다.

• 두 번째 다중 집합을 반복한다.
• 각 항목에 대해 key와 value를 가져오고, 만약 첫 번째 다중집합이 두 번째 다중집합의 key를 가지고 있지 않다면, 해당 value를 합집합의 값에 더한다.

• 마지막으로 교집합을 합집합으로 나누어 유사도를 계산한 후 65536을 곱하여 그 결과를 정수로 반환한다.

결론!