[프로그래머스/Java] Lv.2 - [1차] 뉴스 클러스터링

📝 문제 설명

두 문자열 사이의 자카드 유사도를 계산하는 문제입니다. 일반적인 집합과 달리 이 문제에서는 다중집합(Multiset)의 개념을 적용해야 합니다.

• 문자열을 두 글자씩 끊어서 다중집합의 원소로 만듭니다.
• 영문자로만 구성된 쌍만 유효하며, 숫자나 특수문자가 포함된 쌍은 버립니다.
• 대소문자 차이는 무시합니다.
• 자카드 유사도 $J(A, B)$는 두 집합의 교집합 크기를 합집합 크기로 나눈 값입니다. (둘 다 공집합일 경우 1로 정의)
• 최종 결과값에 65536을 곱한 후 소수점 아래를 버리고 정수형으로 반환합니다.

---

💡 접근 방식

1. 전처리 및 원소 추출

문자열 전체를 toUpperCase()로 변환하여 대소문자 구분을 없앴습니다. 이후 반복문을 돌며 substring(i, i+2)를 통해 두 글자씩 추출했습니다. 이때 정규식(Pattern.matches)을 활용해 두 글자가 모두 알파벳인 경우만 필터링했습니다.

2. 다중집합 구현 (ArrayList vs HashMap)

처음에는 ArrayList와 remove() 메서드를 활용해 교집합을 구하려 했으나, 데이터가 많아질수록 효율성이 떨어질 수 있다는 점을 고려했습니다. 또한 중복된 원소의 개수를 관리하기 위해 HashMap<String, Integer>를 선택했습니다.

• key: 추출된 문자열 쌍 (ex: "FR")
• value: 해당 쌍이 나타난 횟수

3. 교집합과 합집합의 수리적 계산

다중집합에서 교집합과 합집합의 크기를 구하는 가장 효율적인 방법은 각 원소의 '빈도수'를 비교하는 것입니다.

• 교집합(Intersection): 두 맵에 공통으로 존재하는 키에 대해, 두 빈도수 중 최솟값(Math.min)을 합산합니다.
• 합집합(Union): 1. 두 맵에 공통으로 존재하는 키는 두 빈도수 중 최댓값(Math.max)을 합산합니다.
  2. 한쪽에만 존재하는 키는 그 빈도수를 그대로 합산합니다.
     (또는 A의 총 크기 + B의 총 크기 - 교집합 크기 공식을 사용할 수 있습니다.)

---

💻 구현 코드 (Java)

import java.util.*;
import java.util.regex.*;

class Solution {
    public int solution(String str1, String str2) {
        
        String upStr1 = str1.toUpperCase();
        String upStr2 = str2.toUpperCase();
        
        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        
        for(int i=0; i < upStr1.length() - 1; i++) {
            String sub = upStr1.substring(i, i+2);
            if(Pattern.matches("^[A-Z]*$", sub)) {
                map1.put(sub, map1.getOrDefault(sub, 0) + 1);
            }
        }
        
        for(int i=0; i < upStr2.length() - 1; i++) {
            String sub = upStr2.substring(i, i+2);
            if(Pattern.matches("^[A-Z]*$", sub)) {
               map2.put(sub, map2.getOrDefault(sub, 0) + 1);
            }
        }
        
        if(map1.isEmpty() && map2.isEmpty()) return 65536;
        
        double intersect = 0;
        double union = 0;
        
        for(String key : map1.keySet()){
            if(map2.containsKey(key)) {
                int size1 = map1.get(key);  
                int size2 = map2.get(key);
                intersect = intersect + Math.min(size1, size2);
            }
        }
        
        for(String key : map1.keySet()){
            if(map2.containsKey(key)) {
                int size1 = map1.get(key);  
                int size2 = map2.get(key);
                union = union + Math.max(size1, size2);
            }
            else {
                union += map1.get(key);
            }
        }
        
        for(String key : map2.keySet()) {
            if(!map1.containsKey(key)) {
                union += map2.get(key);
            }
        }
        
        return (int)(intersect / union * 65536);
    }
}

✨ 느낀 점

✅ 0으로 나누기(Divide by Zero) 주의

합집합이 0인 경우(두 문자열 모두 유효한 쌍이 없을 때)를 처리하지 않으면 ArithmeticException이 발생합니다. 문제 조건에 따라 공집합일 때 65536을 즉시 반환하도록 예외 처리를 해주는 것이 중요했습니다.

✅ 형변환의 디테일

int 타입끼리 나눗셈을 하면 소수점이 증발하여 결과가 0이 되어버립니다. double 타입을 사용하여 계산을 진행한 후, 마지막에 (int)로 형변환을 해줌으로써 정확한 유사도를 구할 수 있었습니다.

✅ 데이터 구조의 선택

ArrayList를 쓸 때보다 HashMap을 썼을 때 다중집합의 개념이 훨씬 명확하게 코드로 표현되었습니다. 원소의 개수를 관리해야 하는 문제에서는 Map 자료구조가 매우 강력하다는 것을 다시 한번 느꼈습니다.

---