Question

기본 테스트케이스 3번은 65536이 맞지 않나요?

자카드 유사도에 대해 설명하는 부분에서는 중복 원소가 있을 경우 합집합은 둘 중 원소 개수가 많은 것을 넣으면 되는 걸로 돼있는데
문자열 예시를 막상 보면 ("FRANCE", "french")에서
"FR", "NC" 이 둘은 중복돼 2개씩 처리돼야 하는데 합집합에 그냥 하나씩만 들어간 것으로 보이는데요,
그럼 세번째 케이스의 ("aa1+aa2", "AAAA12")도 "AA" 하나만 취급돼,
합집합 = 1, 교집합 = 1 결국 65536이 나와야 하는 것 아닌가요?

작성중인 코드―Solution.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import java.util.*;


class Solution
{
    public int solution(String s1, String s2)
    {
        //s1 = adjustString(s1);
        //s2 = adjustString(s2);
        return (int)(jaccard2(s1.toLowerCase(), s2.toLowerCase()) * 65536);
    }

    double jaccard(String s1, String s2)
    {
        int l1 = s1.length(), l2 = s2.length();
        double r = 0;
        String tmp = "";
        HashMap<String, Integer> set1 = new HashMap<>(), set2 = new HashMap<>();
        HashMap<String, Integer> intersection = new HashMap<>(), union = new HashMap<>();
        int intersectionCnt = 0, unionCnt = 0;

        for (int i = 0; i < l1 - 1; i ++)
        {
            tmp = s1.substring(i, i + 2);
            if (set1.containsKey(tmp))
                set1.replace(tmp, set1.get(tmp) + 1);
            else
            {
                set1.put(tmp, 1);
                if (!union.containsKey(tmp))
                    union.put(tmp, 0);
            }
        }
        for (int i = 0; i < l2 - 1; i ++)
        {
            tmp = s2.substring(i, i + 2);
            if (set2.containsKey(tmp))
                set2.replace(tmp, set2.get(tmp) + 1);
            else
            {
                set2.put(tmp, 1);
                if (union.containsKey(tmp))
                    intersection.put(tmp, 0);
            }
        }

        for (String i:intersection.keySet())
        {
            intersectionCnt += Math.min(set1.get(i), set2.get(i));
        }
        for (String u:union.keySet())
        {
            unionCnt += Math.max(0, 0);
        }


        return r;
    }

    double jaccard2(String s1, String s2)
    {
        int l1 = s1.length(), l2 = s2.length();
        char c1, c2;
        HashSet<String> intersection = new HashSet<>(), union = new HashSet<>(), set1 = new HashSet<>();
        String tmp = "";

        for (int i = 0; i < l1 - 1; i ++)
        {
            c1 = s1.charAt(i);
            c2 = s1.charAt(i + 1);
            if ('a' <= c1 && c1 <= 'z' && 'a' <= c2 && c2 <= 'z')
            {
                tmp = s1.substring(i, i + 2);
                set1.add(tmp);
                union.add(tmp);
            }
        }
        for (int i = 0; i < l2 - 1; i ++)
        {
            c1 = s2.charAt(i);
            c2 = s2.charAt(i + 1);
            if ('a' <= c1 && c1 <= 'z' && 'a' <= c2 && c2 <= 'z')
            {
                tmp = s2.substring(i, i + 2);
                union.add(tmp);
                if (set1.contains(tmp))
                    intersection.add(tmp);
            }
        }
        if (union.size() == 0)
            return 1;
        return (double)intersection.size() / union.size();
    }
}

Answer 1

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.

Answer 2

오래 되어서 푸셨을거 같긴한데 남겨봅니다.
저도 처음에 잘못 이해하고 풀어서 조금 시간이 걸렸는데, "그럼 세번째 케이스의 ("aa1+aa2", "AAAA12")도 "AA" 하나만 취급돼" << 이 부분에서 오류가 있는데요
첫 문자열을 두 글자씩 나눠보면, [aa, a1, 1+, +a, aa, a2]로 숫자, 특문을 제외하면 [aa, aa]로 나옵니다.
마찬가지로 두번째 문자열도 해 보면 [AA, AA, AA, A1 12]로 숫자, 특문 제외 시 [AA, AA, AA]이네요. 즉, 2/3 * 65536으로 43690이 나오게 됩니다.

ingzart

2021.8.19 19:38

기본 테스트케이스 3번은 65536이 맞지 않나요?

작성중인 코드―Solution.java

2 개의 답변

tae100k

2021.9.8 12:26

김영길

2021.9.16 22:59

답변 쓰기

이 입력폼은 마크다운 문법을 지원합니다.