[프로그래머스(Programmers)] 뉴스 클러스터링 (java) /2018 KAKAO BLIND RECRUITMENT

안녕하세요. 오늘은 프로그래머스의 뉴스 클러스터링 문제를 풀어보겠습니다. 이 문제는 2018년도 KAKAO BLIND RECRUITMENT에서 출제되었습니다.

문제 링크

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

문제 풀이

✔ n(A∪B) = n(A) + n(B) - n(A∩B)

합집합을 구하는 것이 까다롭다고 느껴졌는데, 찬찬히 생각해보니 직접 합집합을 구하지 말고 n(A∪B) = n(A) + n(B) - n(A∩B) 공식을 이용해 개수를 구하면 되겠다는 생각이 들었습니다.

전체 코드

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        int union = 0;       //합집합
        int intersect = 0;   //교집합
        final int constant = 65536;
        
        ArrayList<String> split1 = split(str1);
        ArrayList<String> split2 = split(str2);
        
        if (split1.size() == 0 && split2.size() == 0) {
            return 1 * constant;
        } else if (split1.size() == 0 && split2.size() != 0) {
            return 0 * constant;
        } else if (split1.size() != 0 && split2.size() == 0) {
            return 0 * constant;
        }
        
        HashMap<String, Integer> map1 = makeMap(split1);
        HashMap<String, Integer> map2 = makeMap(split2);
        
        ArrayList<String> keySet = new ArrayList<>(map1.keySet());
        
        //교집합 구하는 과정
        for (String key : keySet) {
            if (map2.containsKey(key)) {
                if (map1.get(key) != 1 && map2.get(key) != 1) {
                    intersect += Math.min(map1.get(key), map2.get(key));
                } else {
                    intersect += 1;
                }
            } else {
                continue;
            }
        }
        
        //합집합 구하는 과정
        union = split1.size() + split2.size() - intersect;
        
        return constant * intersect / union;
    }
    
    private ArrayList<String> split(String str) {
        StringBuilder sb = new StringBuilder();
        String str1 = str.toLowerCase();
        
        ArrayList<String> split = new ArrayList<>();
        
        for(int i = 0; i < str1.length(); i++) {
            if(i < str1.length() - 1) {
                char a = str1.charAt(i);
                char b = str1.charAt(i + 1);
                
                if((a >= 97 && a <= 122) && (b >= 97 && b <= 122)) {
                    sb.append(a);
                    sb.append(b);
                    
                    split.add(sb.toString());
                    
                    sb.delete(0, sb.length());
                }
            }
        }
        
        Collections.sort(split);
        
        return split;
    }
    
    private HashMap<String, Integer> makeMap(ArrayList<String> str) {
        HashMap<String, Integer> map = new HashMap<>();
        
        for(String s : str) {
            if(map.containsKey(s)) {
                int cnt = map.get(s);
                map.put(s, cnt + 1);
            } else {
                map.put(s, 1);
            }
        }
        
        return map;
    }
}

느낀점

조금만 생각해도 풀 수 있었어서 재밌었던 문제였습니다.