[프로그래머스/자바] 뉴스 클러스터링 풀이 - 2018 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2018 KAKAO BLIND RECRUITMENT 1차 Level 2 문제다.

 

 

HashMap을 사용해 간단히 구현했다.

 

str1, str2의 집합을 HashMap으로 각각 생성한다.

map에 자른 문자열을 key로, 문자열 출현횟수를 value로 저장한다.

문자열을 자르고 map에 저장하는 함수 stringCut을 만들었다.

String의 문자 하나씩 탐색해서 현재 문자와 그 다음 문자가 알파벳인 경우만 map에 넣는다.

그리고 HashMap의 getOrDefult 함수를 사용해 출현횟수를 저장한다.

 

str1, str2 모두 각 map에 저장했다면 

합집합의 개수와 교집합의 개수를 구한다.

 

 

먼저 교집합은 두 집합 모두 속하는 원소를 찾는 것이므로 하나의 map만을 탐색해도 된다.

나는 map1의 key를 통해 map2에도 동일한 key가 있는지 containsKey를 통해 확인했다.

 

문제의 위 조건을 만족하기 위해,

만약 map2에도 있다면 map1과 map2에서의 key 출현횟수 중 작은 것을 교집합 갯수로 count 한다.

 

 

합집합은 map1, map2에 있는 원소 모두를 count해야 하므로 map1, map2 모두 탐색해야 한다.

먼저 map1에서 key가 map1에만 있다면 map1의 key 출현횟수를 더해주고,

map2에도 있다면 map1과 map2에서의 key 출현횟수 중 큰 것을 합집합 갯수로 count 한다. (위의 조건 만족)

그리고 이후에 map2를 탐색할 때 중복해서 count하는 것을 방지하기 위해 map2에서 key를 삭제해줘야 한다.

 

map1의 key를 모두 탐색했다면 map2를 탐색한다.

이때 map1과 중복되는 원소는 이미 다 삭제된 상태이므로

map2에만 존재하는 원소가 남아있을 것이다.

즉 key가 아닌 value만 탐색해 모두 count해줘도 된다.

 

 

합집합과 교집합의 개수 모두 구했다면 두개를 나누고 문제에서 요구하는 대로 65536을 곱한 정수값만 반환하면 된다.

HashMap으로 출현횟수를 value로 저장해주면 어렵지 않게 풀 수 있는 문제였다.

 

 

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        // 자른 문자열, 출현횟수
        HashMap<String, Integer> map1 = new HashMap<>();
        HashMap<String, Integer> map2 = new HashMap<>();
        
        // 모두 소문자로 변경
        stringCut(str1.toLowerCase(), map1);
        stringCut(str2.toLowerCase(), map2);
        
        if(map1.size() == 0 && map2.size() == 0)
            return 65536; // 1 * 65536
        
        int union = getUnion(map1, map2);
        int intersection = getIntersection(map1, map2);
        
        return (int)(((double)union / intersection) * 65536);
    }
    
    // 두 글자씩 끊어서 map에 넣기
    static void stringCut(String str, HashMap<String, Integer> map) {
        for(int i=0;i<str.length() - 1;i++) {
            char now = str.charAt(i);
            char next = str.charAt(i + 1);
            
            if(now < 'a' || now > 'z')
                continue;
            if(next < 'a' || next > 'z') {
                i++;
                continue;
            }
            
            StringBuilder sb = new StringBuilder();
            sb.append(now).append(next);
            map.put(sb.toString(), map.getOrDefault(sb.toString() , 0) + 1);
        }
    }
    
    // 교집합의 개수 구하기
    static int getUnion(HashMap<String, Integer> map1, HashMap<String, Integer> map2) {
        int union = 0;
        
        for(String s : map1.keySet()) {
            if(!map2.containsKey(s)) 
                continue;
            // 두 집합에 모두 존재한다면 원소의 개수가 적은 것을 포함
            union += Math.min(map1.get(s), map2.get(s));
        }
        
        return union;
    }
    
    // 합집합의 개수 구하기
    static int getIntersection(HashMap<String, Integer> map1, HashMap<String, Integer> map2) {
        int intersection = 0;
        
        for(String s : map1.keySet()) {
            if(!map2.containsKey(s)) 
                intersection += map1.get(s);
            else {
                // 두 집합에 모두 존재한다면 원소의 개수가 많은 것을 포함
                intersection += Math.max(map1.get(s), map2.get(s));
                map2.remove(s);
            }
        }
        
        // map1과 겹치는 걸 삭제했기 때문에 바로 더해줌
        for(int i : map2.values()) 
            intersection += i;
        
        return intersection;
    }

}