뉴스 클러스터링_복습

2026.08.05

문제 풀이

나의 코드

---

소요 시간: 1시간 42분
시간 복잡도: $O(n)$

---

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

class Solution {
    public int solution(String str1, String str2) {
        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        Map<String, Integer> unionMap = new HashMap<>();
        
        float union = 0;
        float intersection = 0;
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str1.length() - 1; i++) {
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i + 1);
            if (Character.isLetter(c1) && Character.isLetter(c2)) { // 문자일 때
                sb.append(c1);
                sb.append(c2);
                String s = sb.toString().toUpperCase();
                map1.put(s, map1.getOrDefault(s, 0) + 1);
                unionMap.put(s, unionMap.getOrDefault(s, 0) + 1);
                sb.setLength(0);
            }
        }
        for (int i = 0; i < str2.length() - 1; i++) {
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i + 1);
            if (Character.isLetter(c1) && Character.isLetter(c2)) { // 문자일 때
                sb.append(c1);
                sb.append(c2);
                String s = sb.toString().toUpperCase();
                map2.put(s, map2.getOrDefault(s, 0) + 1);
                sb.setLength(0);
            }
            else {
                sb.setLength(0);
            }
        }
        
        for (String key : map2.keySet()) {
            if (unionMap.get(key) != null) { // 해당 값이 이미 존재할 때
                int n = Math.max(unionMap.get(key), map2.get(key));
                unionMap.put(key, n);
            }
            else {
                unionMap.put(key, map2.get(key));
            }
        }
        
        for (String key : unionMap.keySet()) {
            union += unionMap.get(key);
        }
        
        for (String key : map1.keySet()) {
            if (map2.containsKey(key)) {
                intersection = intersection + Math.min(map1.get(key), map2.get(key));
            }
        }

        if (union == 0) {
            return 65536;
        }
        return (int)(intersection / union * 65536);
    }
}

AI 코드

---

시간 복잡도: $O(n)$
코드 분석

2개의 알파벳 조합으로 가질 수 있는 경우의 수 26*26크기의 배열을 만들어서
해당하는 인덱스 값을 증감시켰음
해당 배열을 통해 intersection과 union값을 얻어 계산

---

class Solution {
    private static final int SIZE = 26 * 26;

    public int solution(String str1, String str2) {
        int[] cnt1 = countPairs(str1);
        int[] cnt2 = countPairs(str2);

        int intersection = 0;
        int union = 0;
        for (int i = 0; i < SIZE; i++) {
            intersection += Math.min(cnt1[i], cnt2[i]);
            union        += Math.max(cnt1[i], cnt2[i]);
        }

        if (union == 0) {                 // 두 집합 모두 공집합 → J = 1
            return 65536;
        }
        return intersection * 65536 / union;   // 정수 나눗셈 = 절삭, 오차 없음
    }

    private int[] countPairs(String s) {
        int[] cnt = new int[SIZE];
        for (int i = 0; i < s.length() - 1; i++) {
            char a = s.charAt(i);
            char b = s.charAt(i + 1);
            if (isAlpha(a) && isAlpha(b)) {
                int idx = (toUpper(a) - 'A') * 26 + (toUpper(b) - 'A');
                cnt[idx]++;
            }
        }
        return cnt;
    }

    private boolean isAlpha(char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    }

    private char toUpper(char c) {
        return (c >= 'a' && c <= 'z') ? (char) (c - 32) : c;
    }
}

문제 풀이 후기

이전부터 느끼는 점이지만 AI는 배열의 활용을 정말 잘 하는 것 같다.
26 * 26 크기의 배열만 하더라도 생각지도 못한 방향이었다.

나의 코드에서 개선점이 꽤나 많이 보여졌다.

첫번째, float의 사용 대신 intersection에 65536을 먼저 곱한 후
union으로 나누어 리턴했으면 더 안전하게 연산이 가능하다.

둘째, else sb.setLength(0) 구문이 필요가 없다.
sb.append()는 if문 안에서만 하고 있기 때문이다.

셋째, unionMap이 필요하지 않다.
sets1.size() + sets2.size() - intersection으로 union을 바로 얻을 수 있다.
수학이 중요한 이유

넷째, isLetter()는 é나 한글의 경우에도 true를 리턴하기 때문에
알파벳 범위를 벗어나게 된다.
따라서 'a'~'z', 'A'~'Z' 범위 검사가 더 적합하다.

다섯째, unionMap.get(key) != null보다는 위에서 사용한 코드인
containsKey()를 사용하는 것이 더 적합하다.

코드를 작성하면서 값이 제대로 나오지 않아, 리턴값을 intersection, union 만도 사용해보면서 오류 후보를 좁혀나갔다.

해당 방식으로 하나하나 어떤 부분에 오류가 있는지 천천히 탐색하면
오늘처럼 AI를 사용하지 않고 스스로 문제를 해결할 수 있을 것이다.