[PGM_17677] 뉴스 클러스터링 (java)

문제링크

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

코딩테스트 연습 - [1차] 뉴스 클러스터링

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 자료구조 Map을 사용

이 문제는 2개의 문자열에 대하여 2문자씩 연속하는 값으로 문자열 집합을 구성한다. 2개의 집합에 대하여 교집합을 합집합으로 나눈 값을 65536을 곱하고 소수점을 버려서 뽑아내는 문제이다. 집합과 다른점은 중복을 허용한다는 점이다. 따라서 Map으로 집합을 표현해주었다. key값은 집합과 동일하게 중복된 값이 올수 없다. 따라서 key로 들어가는 문자를 표현하였고, value값에 해당하는 문자가 포함된 개수를 넣어주었다. 이 때 문자열에 대해서만 key 값으로 들어갈 수 있으므로 숫자 및 특수문자가 오는 경우는 걸러주기 위해 Character.isAlphabetic()을 사용하였고 대소문자를 구분하지 않기때문에 모두 소문자로 만들어서 구현해주었다.

 

합집합의 개수와 교집합의 개수를 구해주는 방법은 구성된 두 집합의 모든 문자열의 개수에서 교집합의 수를 빼준 것이 합집합이 된다. 따라서, 교집합만 구해주면 합집합을 구할 수 있다. 교집합은 구해진 두개의 map중 하나의 map에 있는 키값을 모두 돌아보며 또 다른 map에 있는지 확인하여 추가할 수 있다. 이 때 중복이 허용되기 때문에 Math.min(a,b)를 활용하여 최대한 많이 겹칠 수 있는 경우를 찾아서 넣어주면된다. 

구현코드

package pgm_17677;

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

public class Solution {

    public  int solution(String str1, String str2) {
        Map<String, Integer> first = makeMultiSet(str1);
        Map<String, Integer> second = makeMultiSet(str2);
        if(first.size() == 0 && second.size() == 0)
            return 65536;

        Set<String> firstKeySet = first.keySet();
        Set<String> secondKeySet = second.keySet();

        int intersection = 0;
        for(String key : firstKeySet){
            if(!second.containsKey(key))
                continue;
            intersection += Math.min(first.get(key),second.get(key));
        }

        int union = -1 * intersection;
        for(String key : firstKeySet){
            union += first.get(key);
        }
        for(String key : secondKeySet){
            union += second.get(key);
        }

        return (int)((intersection/(union*1.0))*65536);
    }
    public Map<String, Integer> makeMultiSet(String str){
        Map<String, Integer> multiSet = new HashMap<>();
        for(int i = 0; i < str.length()-1; i++){
            if(!Character.isAlphabetic(str.charAt(i)) || !Character.isAlphabetic(str.charAt(i+1)))
                continue;

            String key = String.valueOf(Character.toLowerCase(str.charAt(i))) + String.valueOf(Character.toLowerCase(str.charAt(i+1)));
            int value = 0;
            if(multiSet.containsKey(key)){
                value = multiSet.get(key);
            }
            multiSet.put(key,value+1);
        }

        return multiSet;
    }

}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)