2018 카카오 블라인드 모집 - 뉴스 클러스터링

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

자카드 유사도란? 

자카드 유사도란 두 집합 A 와 B 가 있을 때, (교집합의 원소의 개수/ 합집합의 원소의 개수) 로 정의된다.

A= {1, 2, 3}, 집합B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로, 집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다.  

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 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가 된다.

 

전처리 과정 - 문자열을 모두 대문자로 바꾸기

문제의 입력 형식 중 다음과 같은 조건이 있다.

• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

따라서 문자열을 입력받으면, 미리 그 문자열을 모두 대문자로 바꾸기로 한다. 대문자로 바꾼데에는 이유가 있는데, 후에서 기술하겠다.

static int solution(String str1, String str2) {
    str1 = str1.toUpperCase();
    str2 = str2.toUpperCase();
}

HashMap 을 사용해 집합의 개수 구하기

문자열을 분리한 후의 집합의 원소와 원소의 개수를 관리하기 위해 HashMap 을 사용했다.

HashMap 의 키값은 분리된 문자열의 각 원소이고, value 값은 그 원소의 개수를 나타내는 정수값이다.

 

즉 어떤 집합 A= {"FR","RA","AN","NC","CE"} 이 있을 때, "FR" 과 같은 원소가 키 값이 되고 그 원소의 출현횟수가 value 값이 된다.

 

문자열을 분리해 HashMap 만들기

그 다음 문자열을 2개씩 끊어가며 집합을 만들어준다. 이전에 집합은 HashMap 으로 관리한다고 했는데, 이 때 HashMap 의 키값은 Integer, 즉 정수형으로 잡아준다. 

String을 분리하게 되면 String 특성 상 힙 메모리에 계속 할당되기 때문이다. 

전처리 과정에서 문자열을 모두 대문자로 바꿔줬었는데, 대문자는 모두 2자리의 정수로 표현이 가능하다.

따라서 첫 번째 문자의 정수값에 100을 곱한뒤, 두 번째 문자의 정수값을 더한 결과를 키 값으로 사용한다

 

static HashMap<Integer, Integer> getSet(String str) {
    HashMap<Integer, Integer> hashMap = new HashMap<>();

    //문자열을 분리해가며 원소를 만든다
    for (int i = 0; i < str.length() - 1; i++) {
        if (canPut(str.charAt(i), str.charAt(i + 1))) {
            int key = (str.charAt(i) * 100) + str.charAt(i + 1);
            hashMap.put(key, hashMap.getOrDefault(key, 0) + 1);
        }
    }
    
    return hashMap;
}

FRANCE 를 분리한다고 쳤을 때, 나오는 원소 중 "FR" 의 키값은 F(70) * 100 + R(82) = 7082가 되는 것이다.

 

교집합 원소 개수 구하기

 

static int getCommonSet(HashMap<Integer, Integer> first, HashMap<Integer, Integer> second) {
    int sum = 0;
    for (int key : first.keySet()) {
        if (second.containsKey(key)) {
            sum += Math.min(first.get(key), second.get(key));
        }
    }
    return sum;
}

교집합은 하나의 집합만 검사하면 된다. 만약 다른 집합도 같은 키(원소) 를 가지고 있으면, 다중집합의 원리에 따라 두 원소 중 개수가 적은 원소를 더해준다.

 

합집합 원소 개수 구하기

 

static int getTotalSet(HashMap<Integer, Integer> first, HashMap<Integer, Integer> second) {
    int sum = 0;
    for (int key : first.keySet()) {
        if (second.containsKey(key)) {
            sum += Math.max(first.get(key), second.get(key));
        } else {
            sum += first.get(key);
        }
    }
    for (int key : second.keySet()) {
        if (!first.containsKey(key)) {
            sum += second.get(key);
        }
    }
    return sum;
}

합집합은 두 집합의 모든 원소를 나열해야 하므로, 우선 두 집합간의 동일한 원소에 대해 계산한다. 만약 두 집합에 모두 존재하는 원소가 있으면, 다중집합 원리에 따라 원소의 개수가 더 큰 값을 더한다.

 

그 다음 두 번째 집합 중 첫 번째 집합에 포함되있지 않은 원소의 개수들을 모두 더해준다.

 

전체코드

 

public class NewsClustering {
    static final int MUL = 65536;

    public static void main(String[] args) throws IOException {
        System.out.println(solution("E=M*C^2", "e=m*c^2"));
        System.out.println((int) 'F');
        System.out.println((int) 'R');
    }


    static int solution(String str1, String str2) {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        HashMap<Integer, Integer> firstMap = getSet(str1);
        HashMap<Integer, Integer> secondMap = getSet(str2);
        if (firstMap.isEmpty() && secondMap.isEmpty()) {
            return MUL;
        }
        int common = getCommonSet(firstMap, secondMap);
        int total = getTotalSet(firstMap, secondMap);
        double temp = (double) common / total;

        return (int) (temp * MUL);
    }


    static int getCommonSet(HashMap<Integer, Integer> first, HashMap<Integer, Integer> second) {
        int sum = 0;
        for (int key : first.keySet()) {
            if (second.containsKey(key)) {
                sum += Math.min(first.get(key), second.get(key));
            }
        }
        return sum;
    }

    static int getTotalSet(HashMap<Integer, Integer> first, HashMap<Integer, Integer> second) {
        int sum = 0;
        for (int key : first.keySet()) {
            if (second.containsKey(key)) {
                sum += Math.max(first.get(key), second.get(key));
            } else {
                sum += first.get(key);
            }
        }
        for (int key : second.keySet()) {
            if (!first.containsKey(key)) {
                sum += second.get(key);
            }
        }
        return sum;
    }

    static HashMap<Integer, Integer> getSet(String str) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();

        //문자열을 분리해가며 원소를 만든다
        for (int i = 0; i < str.length() - 1; i++) {
            if (canPut(str.charAt(i), str.charAt(i + 1))) {
                int key = (str.charAt(i) * 100) + str.charAt(i + 1);
                hashMap.put(key, hashMap.getOrDefault(key, 0) + 1);
            }
        }

        return hashMap;
    }

    static private boolean canPut(char a, char b) {
        return a >= 'A' && a <= 'Z' && b >= 'A' && b <= 'Z';
    }
}