Programmers 뉴스 클러스터링 java 풀이

1. 문제 설명

문제 링크

2. 접근 방식

(1) HashSet에 나오는 모든 부분 문자열을 저장한다.

(2) map1 , map2는 HashMap으로서 각 문자열의 문자가 key, 그 문자가 나오는 개수가 value이다.

(3) hashSet에 저장되어 있는 문자를 하나씩 꺼낸다. 해당 문자의 개수를 map1과 map2에서 꺼내서, 합집합과 교집합을 계산한다.
합집합: 둘 중 더 개수가 많은 쪽의 개수를 더한다.
교집합: 둘 중 하나라도 값이 존재하지 않으면 넘어간다. 둘 다 해당 값을 가지고 있다면 개수가 더 적은 쪽의 개수를 더한다.

3. 코드 분석

import java.io.*;
import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        HashSet<String> set = new HashSet<>();
        HashMap<String, Integer> map1 = new HashMap<>();
        HashMap<String, Integer> map2 = new HashMap<>();
        split_str(str1, map1, set); split_str(str2, map2, set);



        // 2. 교집합, 합집합 구하기
        double union = 0;
        double inter = 0;
        for(String temp : set){
            int cnt1 = map1.get(temp) == null ? 0 : map1.get(temp);
            int cnt2 = map2.get(temp) == null ? 0 : map2.get(temp);

            union += Math.max(cnt1, cnt2);
            if(cnt1 == 0 || cnt2 == 0) continue;
            else{
                inter += Math.min(cnt1,cnt2);
            }

        }


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

        return (int)((inter/union)*65536) ;
    }
    // 1. 글자 잘라서 map에 넣기
    public void split_str(String str, HashMap<String,Integer> map, HashSet<String> set) {
        for(int i = 2; i <= str.length(); i+=1){
            boolean isValid = true;
            String now = str.substring(i-2, i);
            // 97, 122, 65, 90
            for(int j = 0; j<2; j++){
                if((now.charAt(j)>= 97 && now.charAt(j)<= 122)||
                    (now.charAt(j)>= 65 && now.charAt(j)<= 90)) continue;
                isValid = false;
            }
            if(isValid) {
                set.add(now.toLowerCase());
                map.compute(now.toLowerCase(),(key,oldValue) -> oldValue== null? 1 : oldValue+1);
            }
        }
    }
}

4. 성장 하기

다른 사람의 풀이로 공부해보겠다.

class Solution {
    // Character.MAX_VALUE는 65535로, 여기에 1을 더한 65536을 MULTIPLIER로 설정
    private static final Integer MULTIPLIER = Character.MAX_VALUE + 1;

    public int solution(String str1, String str2) {
        // 두 입력 문자열을 소문자로 변환
        String word1 = str1.toLowerCase();
        String word2 = str2.toLowerCase();

        // 각 문자열을 부분집합으로 그룹화하여 Map으로 반환
        Map<String, Long> words1 = group(word1);
        Map<String, Long> words2 = group(word2);

        // 두 문자열의 교집합 크기를 계산
        Integer intersection = getIntersection(words1, words2);
        // 두 문자열의 합집합 크기를 계산
        Integer union = getUnion(words1, words2);

        // 교집합과 합집합이 모두 0인 경우, MULTIPLIER 반환 (두 문자열이 모두 비어있을 경우)
        if (intersection.equals(union) && union.equals(0)) {
            return MULTIPLIER;
        }

        // 교집합 크기를 합집합 크기로 나누고, MULTIPLIER를 곱하여 결과 반환
        return (int) (intersection.doubleValue() / union.doubleValue() * MULTIPLIER);
    }

    // 주어진 문자열에서 2글자씩 끊어 부분집합을 만들고, 각 부분집합의 빈도수를 계산하는 함수
    private Map<String, Long> group(String word) {
        // 문자열의 길이에서 1을 뺀 범위에서 반복 (마지막 2글자까지 포함하기 위해)
        return IntStream.range(0, word.length() - 1)
            // 각 인덱스에서 2글자씩 부분 문자열 생성
            .mapToObj(index -> word.substring(index, index + 2))
            // 생성된 2글자 부분 문자열이 모두 알파벳인지 확인
            .filter(text -> text.chars().allMatch(character -> Character.isAlphabetic((char) character)))
            // 알파벳 부분 문자열을 Map으로 그룹화, 각 문자열의 빈도를 계산하여 Map으로 반환
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    }

    // 두 Map에서 공통으로 존재하는 2글자 부분 문자열의 최소 빈도를 합산하여 교집합 크기를 계산하는 함수
    private Integer getIntersection(Map<String, Long> words1, Map<String, Long> words2) {
        return words1.entrySet().stream()
                // words2에도 존재하는 키만 필터링
                .filter(entry -> words2.containsKey(entry.getKey()))
                // 두 Map에서 공통 키의 빈도 중 최소값을 가져옴
                .map(entry -> Math.min(entry.getValue(), words2.get(entry.getKey())))
                // 이 최소값들을 합산하여 교집합 크기를 계산
                .mapToInt(Long::intValue)
                .sum();
    }

    // 두 Map에서 모든 2글자 부분 문자열의 최대 빈도를 합산하여 합집합 크기를 계산하는 함수
    private Integer getUnion(Map<String, Long> words1, Map<String, Long> words2) {
        // words2의 복사본을 생성하여, words1의 값을 병합
        Map<String, Long> copiedWords = new HashMap<>(words2);
        // words1의 각 엔트리에 대해, words2와의 최대 빈도수를 저장
        words1.forEach((key, value) -> copiedWords.put(key, Math.max(value, words2.getOrDefault(key, 0L))));

        // 모든 값을 합산하여 합집합 크기를 계산
        return copiedWords.values().stream()
                .mapToInt(Long::intValue)
                .sum();
    }
}

⛏️Driling

(1)

.filter(text -> text.chars().allMatch(character -> Character.isAlphabetic((char) character)))

용어	설명
text.chars()	여기서 text는 문자열이다. 이 문자열을 IntStream()으로 변환한다. 따라서 다음 Stream에서는 text의 문자 하나하나가 int형태로 chaining에 입력 된다.
.allMatch(n -> predicate(n))	Stream의 주어진 모든 요소가 predicate(n)를 만족한다면 true 아니면 false 반환한다.
Character.isAlphabetic(n)	n이 알파벳에 해당하면 true, 아니면 false 반환

(2)

.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

용어	설명
Collectors.groupingBy(A,B)	Stream의 요소들을 첫 번째 인자를 기준으로 그룹화 한다.
Function.identity()	Stream에서 주어진 입력을 그대로 반환하는 함수 예를 들어, "ab", "ab", "cd"라는 문자열들이 있다면, "ab"는 두 번, "cd"는 한 번 그룹화 된다.
Collectors.counting()	첫 번째 인자로 그룹화 하였을 때, 해당 그룹의 빈도수를 세어서, Map<String, Long> 형태로 반환한다. "ab"라는 문자열이 두 번 등장했으면, counting()은 2를 반환