[Java] 프로그래머스(level-2) - 뉴스 클러스터링

문제 풀이

---

이 문제는 중복을 허용하는 다중집합을 처리할 수 있어야 한다.

아이디어 도출

• HashMap을 사용하여 같은 문자열의 빈도수를 연산한다.
• 중복 허용 다중집합의 특성을 이용하여 교집합, 합집합 개수를 구한다.

중복을 허용하는 다중집합의 특징은 무엇일까?

중복을 허용하는 다중집합의 특징 2가지

• 교집합의 개수는 같은 문자열의 빈도 수 중 작은 빈도 수만큼 증가되어야 한다.
• 합집합의 개수는 같은 문자열의 빈도 수 중 큰 빈도 수만큼 증가되어야 한다.

위 2가지를 통해 교집합과 합집합 개수를 쉽게 구할 수 있다. 이떄, 유의해야 할점은 다음과 같다.

1. HashMap을 2개를 이용하게 될텐데 위 특징을 활용할 Map을 순회할 때 교집합의 개수를 모두 구하고 합집합의 일부 개수를 구한 후, 나머지 Map에서는 합집합의 개수만 덧셈해주면 된다.
2. 기준이 되는 Map에서 교집합 개수와 합집합의 일부 개수를 구하고 처리된 문자열은 제거해야 한다.

위 아이디어를 통해 작성한 코드는 아래에서 확인할 수 있다.

작성 코드

---

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        // ** 이 문제에서는 중복을 허용하는 다중집합을 처리해야 한다.
        int answer = 0;
        
        // 대소문자 구별하지 않기에 모두 대문자로 치환
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        
        // 두글자씩 자른 문자의 빈도 수를 카운트하기 위한 HashMap 선언
        Map<String, Integer> hm1 = new HashMap<>();
        Map<String, Integer> hm2 = new HashMap<>();

        // 교집합 및 합집합 개수를 구할 변수 초기화
        int intersection = 0;
        int union = 0;

        // str1과 str2 문자열을 순회하면서 A~Z까지의 문자에 해당되는 대문자 두글자를 hm1, hm2에 삽입하고 빈도수를 연산한다.
        for(int i=0; i<str1.length()-1; i++) {
            if((65 <= (int)str1.charAt(i) && (int)str1.charAt(i) <= 90) && (65 <= (int)str1.charAt(i+1) && (int)str1.charAt(i+1) <= 90)) {
                String two_str = String.valueOf(str1.charAt(i)) + String.valueOf(str1.charAt(i+1));
                hm1.put(two_str, hm1.getOrDefault(two_str, 0)+1);
            }
        }
        for(int i=0; i<str2.length()-1; i++) {
            if((65 <= (int)str2.charAt(i) && (int)str2.charAt(i) <= 90) && (65 <= (int)str2.charAt(i+1) && (int)str2.charAt(i+1) <= 90)) {
                String two_str = String.valueOf(str2.charAt(i)) + String.valueOf(str2.charAt(i+1));
                hm2.put(two_str, hm2.getOrDefault(two_str, 0)+1);
            }
        }

        // ** hm1, hm2에서 중복 허용 다중집합의 특징을 활용하여 교집합, 합집합의 개수를 구한다.
        // - 교집합의 개수는 같은 문자열의 빈도 수 중 작은 값만큼 증가되어야 한다.
        // - 합집합의 개수는 같은 문자열의 빈도 수 중 큰 값만큼 증가되어야 한다.
        
        // 1. hm1의 원소가 hm2에 존재하는지 확인한다. 
        // 2. hm1의 원소가 hm2에 존재한다면, hm1과 hm2에서 작은 빈도 수를 교집합 개수에 덧셈한다.
        // 3. 또한, hm1과 hm2의 큰 빈도 수를 합집합 개수에 덧셈한다.
        // 4. 이 떄, hm1에서 처리한 같은 문자열은 hm2에서 제거해야 한다.
        // 5. hm1의 원소가 hm2에 존재하지 않는다면 해당 문자열의 빈도수를 합집합 개수에 증가시킨다.
        // 6. 마지막으로 hm2을 순회하면서는 hm1에 존재하지 않는 빈도 수를 합집합 개수에 덧셈하면 된다.
        for(String key : hm1.keySet()) {
            if(hm2.containsKey(key)) {
                intersection += Math.min(hm1.get(key), hm2.get(key));
                union += Math.max(hm1.get(key), hm2.get(key));
                // 처리된 문자 제거
                hm2.remove(key);
            } else {
                union += hm1.get(key);
            }
        }
        for(String key : hm2.keySet()) {
            union += hm2.get(key);
        }

        // 교집합과 합집합 개수가 0이라면 1*65536 값을 반환한다.
        // 최종적으로 교집합/합집합 실수를 65536으로 곱한 후 소수점 아래를 버려서 반환한다.
        if(intersection == 0 && union == 0) {
            answer  = 1 * 65536;
        } else {
            double jaccard = (double) intersection / union;
            System.out.println(jaccard);
            answer = (int) Math.floor(jaccard*65536);
        }

        return answer;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        String str1 = "FRANCE";
        String str2 = "french";
        // String str1 = "E=M*C^2";
        // String str2 = "e=m*c^2";
        // String str1 = "handshake";
        // String str2 = "shake hands";
        // String str1 = "aa1+aa2";
        // String str2 = "AAAA12";

        sol.solution(str1, str2);
    }
}

회고

• ---

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.