문제

Programmers [1차] 뉴스 클러스터링

핵심

• 입력의 크기가 1,000이라 대략 $O(N^2)$이하 알고리즘을 사용한다.
• 두 문자열이 주어질 때, 두 문자열 사이의 자카도 유사도를 구해야 한다. 자카도 유사도란 두 집합의 교집합의 크기를 합집합의 크기로 나눈 값이며 두 글자씩 끊어 다중 집합을 만들 수 있다.
• 예시 입출력 3번이 헷갈렸었다. aa1+aa2 AAAA12 43690이고, 대소문자를 구분하지 않으므로 소문자로 본다면 첫 번째 문자열의 집합은 "aa", "aa"가 나오며 두 번째 문자열 집합은 "aa", "aa", "aa"가 나온다. 따라서 65536 * 2/3 = 43690이 된다. 핵심은 중복 문자 집합을 구분하여 교집합과 합집합을 구해야 한다.
• 중복 집합을 파악하기 위해 특정 원소가 몇 개 있는지 저장해야 한다. Map<String, Integer> 자료구조를 이용하면 해당 키 값에 대해 중복 원소의 개수를 저장할 수 있다.

Map<String, Integer> m = new HashMap<>();

m.put(key, m.getOrDefault(key, 0) + 1);

접근 순서

1. 입력된 문자열을 두 글자씩 끊어 다중 집합 원소로 만든다. 대소문자는 구별하지 않고, 영문자 외 문자가 포함되어 있으면 그 문자는 버린다.
2. Map 자료구조로 다중 집합의 원소를 m1, m2에 각각 저장한다.
3. 교집합을 구한다. 교집합은 m1과 m2가 같은 키 값을 가지는 경우다. 같은 키 값 중 m1과 m2의 최솟값이 교집합이 된다.
4. 합집합을 구한다. 합집합은 m1과 m2가 같은 키 값을 가질 때는 큰 값이 된다. 같은 키가 아닐 경우 해당 키 값을 더하면 합집합이 된다.

• 3, 4번이 중요하고, 코드로 표현하면 아래와 같다.

int findInter(Map<String, Integer> m1, Map<String, Integer> m2) {
	
	int ret = 0;
	for (var key : m1.keySet()) {
		if (m2.containsKey(key)) {
			ret += Math.min(m1.get(key), m2.get(key));
		}
	}
	return ret;
}

int findUnion(Map<String, Integer> m1, Map<String, Integer> m2) {
	
	int ret = 0;
	for (var key : m1.keySet()) {
		if (m2.containsKey(key)) {
			ret += Math.max(m1.get(key), m2.get(key));
		} else {
			ret += m1.get(key);
		}
	}
	for (var key : m2.keySet()) {
		if (!m1.containsKey(key)) {
			ret += m2.get(key);
		}
	}
	return ret;
} 

개선

시간복잡도

• $O(N)$
  

코드

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        
        Map<String, Integer> m1 = createMultiSet(str1.toCharArray());
        Map<String, Integer> m2 = createMultiSet(str2.toCharArray());
        
        if (m1.size() == 0 && m2.size() == 0)
            return 65536;
        
        int a = findInter(m1, m2);
        int b = findUnion(m1, m2);
        
        double jakad = (double) a / b;
        
        return (int)(65536 * jakad);
    }
    
    Map<String, Integer> createMultiSet(char[] chars) {
        
        Map<String, Integer> m = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < chars.length - 1; ++i) {
            sb.setLength(0);
            if (chars[i] >= 'a' && chars[i] <= 'z' && chars[i + 1] >= 'a' && chars[i + 1] <= 'z') {
                sb.append(chars[i]);
                sb.append(chars[i + 1]);
                m.put(sb.toString(), m.getOrDefault(sb.toString(), 0) + 1);
            }
        }
        
        return m;
    }
    
    int findInter(Map<String, Integer> m1, Map<String, Integer> m2) {
        
        int ret = 0;
        for (var key : m1.keySet()) {
            if (m2.containsKey(key)) {
                ret += Math.min(m1.get(key), m2.get(key));
            }
        }
        return ret;
    }
    
    int findUnion(Map<String, Integer> m1, Map<String, Integer> m2) {
        
        int ret = 0;
        for (var key : m1.keySet()) {
            if (m2.containsKey(key)) {
                ret += Math.max(m1.get(key), m2.get(key));
            } else {
                ret += m1.get(key);
            }
        }
        for (var key : m2.keySet()) {
            if (!m1.containsKey(key)) {
                ret += m2.get(key);
            }
        }
        return ret;
    } 
}