조건을 꼼꼼히 읽고 잘 맞춰 코드를 짜면 풀 수 있는 문제였다. 하지만 시간은 짱 많이 걸렸다..
equalsIgnoreCase()
를 사용해서 비교할 수도 있지만, HashMap에서 key를 저장할 때 같은 것으로 인식하게 하기 위해서는 애초에 하나로 통일하고 시작하는 것이 더 낫다.jaccard()
에서는 두 String의 subset
을 구하고 이를 비교해서 similarity
를 계산해낸다.sumOfUnionCounts()
를 그냥 union.size()
로 하면 다중집합 케이스의 경우 제대로 계산이 되지 않는다.getSubset()
에서는 String의 subString
을 차례로 탐색하며 알파벳으로만 이루어진 subString
을 HashMap에 개수와 함께 저장하고 리턴한다.getOrDefault()
메소드가 바로 생각이 나서 적용할 수 있었다.comapreSubsets()
에서는 두 subset
을 O(n^2)의 복잡도로 탐색하며 교집합과 합집합을 알아낸다.key
가 같은 경우, HashMap에서 불러온 두 값 중 작은 값으로 추가한다.key
에 대해 union
의 value
를 최대 카운트로 갱신한다.import java.util.*;
class Solution {
private static final int CONST = 65536;
private Map<String, Integer> union = new HashMap<>();
private int intersectionCount;
public int solution(String str1, String str2) {
str1 = str1.toUpperCase();
str2 = str2.toUpperCase();
double similarity = jaccard(str1, str2);
return (int) (similarity * CONST);
}
private double jaccard(String str1, String str2) {
Map<String, Integer> subset1 = getSubset(str1);
Map<String, Integer> subset2 = getSubset(str2);
if (subset1.size() == 0 && subset2.size() == 0) return 1;
compareSubsets(subset1, subset2);
return (double) intersectionCount / sumOfUnionCounts();
}
private double sumOfUnionCounts() {
return union.values().stream().mapToInt(Integer::valueOf).sum();
}
private Map<String, Integer> getSubset(String str) {
Map<String, Integer> result = new HashMap<>();
for (int i = 0; i < str.length() - 1; i++) {
if (isAlphabet(str.charAt(i)) && isAlphabet(str.charAt(i + 1))) {
String subString = str.substring(i, i + 2);
result.put(subString, result.getOrDefault(subString, 0) + 1);
}
}
return result;
}
private boolean isAlphabet(char ch) {
return ch >= 'A' && ch <= 'Z';
}
private void compareSubsets(Map<String, Integer> subset1, Map<String, Integer> subset2) {
for (String key1 : subset1.keySet()) {
for (String key2 : subset2.keySet()) {
if (key1.equals(key2)) {
intersectionCount += Math.min(subset1.get(key1), subset2.get(key2));
union.put(key1, Math.max(subset1.get(key1), subset2.get(key2)));
} else {
union.put(key1, Math.max(subset1.get(key1), union.getOrDefault(key1, 0)));
union.put(key2, Math.max(subset2.get(key2), union.getOrDefault(key2, 0)));
}
}
}
}
}