프로그래머스_뉴스 클러스터링_day19

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

프로그래머스

오늘은 알고리즘 챌린지 19일 차이다. 오늘도 어제처럼 카카오 블라인드 채용 시험 문제를 가져왔다. 난이도는 중으로 분류되어 적당히 어려웠던 것 같지만, 시간 복잡도를 고려하지 않아도 될 정도로 조건의 범위가 작고, 처음 보는 개념에 대해서도 설명이 상세하게 나와있기 때문에 그대로 코드만 구현할 수 있다면 쉽게 풀 수 있을 것이다. 

문제를 풀기 위한 핵심 키포인트는 아래와 같다. 

1. 교집합 수와 합집합 수가 모두 0인 경우만 자카드 유사도는 1을 리턴한다.
2. 교집합의 개수를 구할 때 다중 집합을 고려하여, 같은 원소에 대해서 교집합 원소는 더 작은 것을, 합집합 원소는 더 큰것을 계산한다.

위의 두 가지 전제가 끝이다. 정말 그대로 구현만 하면 된다. 두 가지 코드를 보여줄 건데, 하나는 있는 그대로 순차적으로 로직을 구현할 거고, 하나는 좀 더 깔끔하게 스트림으로 구현해 보았다. 
1번 소스를 먼저 보고 2번 소스를 보면 이해가 편할것이다. 

 

Java 1

import java.util.*;
class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
	// 대/소문자를 구분하지 않으므로 소문자로 통일 시키자. 
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();

	//각 문자열의 다중 집합과 그 개수를 저장할 맵을 선언한다. 
        Map<String,Integer> str1Map = new HashMap<>();
        Map<String,Integer> str2Map = new HashMap<>();

	//문자열1의 다중 집합을 구한다. 알파벳 소문자의 아스키 코드 범위는 97~122이다.
        for(int i=0; i<str1.length()-1; i++) {
            String temp = str1.substring(i, i+2);
            char [] checked = temp.toCharArray();
            if((int)checked[0] < 97 || (int)checked[0] > 122 || (int)checked[1] < 97 || (int)checked[1] > 122) continue;
            str1Map.put(temp, str1Map.getOrDefault(temp, 0) + 1);
        }
	//문자열2의 다중 집합을 구한다. 알파벳 소문자의 아스키 코드 범위는 97~122이다.
        for(int i=0; i<str2.length()-1; i++) {
            String temp = str2.substring(i, i+2);
            char [] checked = temp.toCharArray();
            if((int)checked[0] < 97 || (int)checked[0] > 122 || (int)checked[1] < 97 || (int)checked[1] > 122) continue;
            str2Map.put(temp, str2Map.getOrDefault(temp, 0) + 1);
        }

	//set을 이용하여 두 다중집합의 합집합을 구한다. 여기서는 중복이 제거되므로, 개수는 밑에서 따로 구한다.
        Set<String> hap = new HashSet<>();
        hap.addAll(str1Map.keySet());
        hap.addAll(str2Map.keySet());
		
        
       //합집합의 원소 개수를 구한다.(더 큰 것)
        int max = 0; 
        for(String s : hap) {
            if(str1Map.containsKey(s) && !str2Map.containsKey(s)) max += str1Map.get(s);
            else if(!str1Map.containsKey(s) && str2Map.containsKey(s)) max += str2Map.get(s);
            else if(str1Map.containsKey(s) && str2Map.containsKey(s)) max += Math.max(str1Map.get(s), str2Map.get(s));
        }

	//교집합의 원소 개수를 구한다. (더 작은 것)
        int gyu = 0; 
        for(String s : str1Map.keySet()) {
            if(str2Map.containsKey(s)) {
                gyu += Math.min(str2Map.get(s), str1Map.get(s));
            }
        }
        
        //두 값이 모두 0인 경우만 예외로 처리한다.
        if(gyu == 0 && max == 0) return 65536;

        answer = (int) (gyu*1.0/max*65536);
        return answer;
    }
}

 

Java 2(Stream)

import java.util.*;
import java.util.stream.*;
import java.util.function.*;
class Solution {
    private static final int exception = Character.MAX_VALUE + 1;
    public int solution(String str1, String str2) {
        String word1 = str1.toLowerCase();
        String word2 = str2.toLowerCase();
        Map<String, Long> words1 = multiGroup(word1);
        Map<String, Long> words2 = multiGroup(word2);

        Integer inspection = getInspection(words1, words2);
        Integer union = getUnion(words1, words2);
        
        if(inspection.equals(union) && union.equals(0)) return exception;

        return (int) (inspection.doubleValue() / union.doubleValue() * exception);
        
    }
    private static Integer getUnion(Map<String, Long> words1, Map<String, Long> words2) {
        Map<String, Long> unionWords2 = new HashMap<>(words2);
        words1.forEach((key, value) -> unionWords2.put(key, Math.max(value, words2.getOrDefault(key, 0L))));

        return unionWords2.values().stream()
                .mapToInt(Long::intValue)
                .sum();
    }

    private static Integer getInspection(Map<String, Long> words1, Map<String, Long> words2) {
        return words1.entrySet().stream()       //words1 맵의 entry를 순회하는 스트림 생성
                .filter(entry -> words2.containsKey(entry.getKey())) //words1의 키를 갖는 words2의 entry를 필터링
                .map(entry -> Math.min(entry.getValue(), words2.get(entry.getKey())))//공통 키를 갖는 요소에 대해서 더 작은 value를 가져온
                .mapToInt(Long::intValue)   //long값을 int로 캐스팅
                .sum();                     //총합을 구하기
    }

    private static Map<String, Long> multiGroup(String word) {
        return IntStream.range(0, word.length()-1)// 0 ~ word.length()-2의 인덱스를 생성하는 정수형 스트림
                .mapToObj(index -> word.substring(index, index+2))//생성한 각 인덱스를 이용하여 2글자씩 끊어 부분 문자열을 추출한다.
                .filter(text -> text.chars().allMatch(character -> Character.isAlphabetic((char) character))) //text.chars()로 각 문자의 intStream을 생성하고 모든 문자가 알파벳인지 확인
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); 
        //추출한 부분 문자열을 그대로 키로 사용(Function.identity())하여 개수별로 그룹화 한다.
    }
}