간단히 문제를 요약하자면…

두 문자열을 받아 영문자에 대한 자카르 유사도를 계산하기

정도로 요약이 되나, 세부적인 사항이 있다.

문제 풀이에 앞서 문제 및 요구사항 정리를 해보자

  • 입력값으로는 2자 이상 1000자 이하의 두 문자열을 입력 받음
  • 입력값에 대한 자카르 유사도를 출력해야함
  • 입력 문자열은 두 글자씩 끊어서 연산에 사용한다.
    • 이 때, 기타 공백이나 숫자, 특수 문자가 포함될 경우 연산에 사용하지 않는다
  • 대소문자 구별을 하지 않는다.

그렇다면 자카르 유사도 란 무엇일까?

자카르 유사도⌗

두 집합 간의 유사도를 검사하느 여러 방법 중 하나로, 수학적 수식으로 표현하면 아래와 같다.

$$J(A,B) = \frac {|A\cap B|}{|A\cup B|} = \frac {|A\cap B|} {|A| + |B| - |A\cap B| } $$

교집합을 합집합으로 나눈 값이다.

그렇다면, 문제에서 자카르 유사도를 어떻게 계산해야 될까?

문제에서는 두 집합의 경우,

입력으로 주어지는 두 문자열의 부분 집합으로

각 문자열을 제약사항(두글자 단위로, 영문만 포함된 문자열)에 맞춰 중복을 허락 하는 집합이다.

풀이⌗

먼저 두 문자 로 이뤄진 부분집합을 다루기 위해 해당하는 객체를 선언을 해주었다

class PartStr {
    private char a;
    private char b;

    public PartStr(char a, char b) {
        this.a = a;
        this.b = b;
    }

    // equals and hashcode 생략
}

다음으론 문자열을 PartStr 부분 집합으로 변환하는 메소드를 작성하였는데

간단하게 문자열을 순회하면서 다음 문자열까지 가져와 둘 다 영문자일 경우에만 부분집합에 추가하였다.

public List<PartStr> strToCharSet(String str) {
    List<PartStr> result = new ArrayList<>();       // 결과로 나올 부분 집합
    str = str.toUpperCase();                        // 대소문자를 무시하고 계산하기 위해 전부 대문자로 변환
    for (int i = 0; i < str.length() - 1; i++) {
        char a = str.charAt(i);
        char b = str.charAt(i + 1);
        if (!isLetter(a) || !isLetter(b)) {         // Character.isLetter 메소드를 사용하여 검사하였음
            continue;
        }
        result.add(new PartStr(a, b));
    }
    return result;
}

이제 두 집합을 추출하였으니, 자카르 유사도를 검사를 해야 한다.

처음 작성시에는 중복 여부에 따른 값 변화를 깊게 생각하질 않아서,

Stream 연산을 통해 곂치는 값만 카운팅을 해주었으나,

중복을 허용하는 집합이기에 다르게 처리를 하였다.

한 집합(A)에 대해서 순차적으로 확인 후(교집합) 다른 집합(B) 에서 제거하는 형식으로 진행하였다.

합집합의 경우 $ |A| + |B| - |A\cap B| $ 이기에

교집합 연산시 처리되지 않는 요소(A)와 제거되지 않은 요소(B)를 모두 더하면 자동으로 나온다.

그리고 소숫점 5자리까지는 정확히 계산하기 위해 BigDecimal을 통해 연산을 진행하였다.

float 를 사용할시 부정확하게 연산될 가능성이 있기에

double 이나 BigDecimal 을 통해 연산을 하는게 좋아보인다.

private float jaccard(Collection<PartStr> partStrs1, Collection<PartStr> partStrs2) {
    //교집합
    List<PartStr> intersection = new ArrayList<>(); // 교집합으로 나올 집합
    //합집합
    List<PartStr> union = new ArrayList<>(); // 합집합으로 나올 결과
    for (PartStr elem : partStrs1) {
        if (partStrs2.contains(elem)) {
            intersection.add(elem);
            partStrs2.remove(elem);
        }
        union.add(elem);
    }
    union.addAll(partStrs2);
    
    BigDecimal intersectionCount = 
        BigDecimal.valueOf(intersection.size());
    BigDecimal unionCount 
        = BigDecimal.valueOf(union.size());
    try {
        return intersectionCount
            .divide(unionCount, 5, RoundingMode.FLOOR)
            .floatValue();
    } catch (Exception e) {
        // 0으로 나뉘는 경우나 연산을 할 수 없는 경우, 문제 내용에 따라 1을 반환하였다.
        return 1L; 
    }
}

참고⌗