2018 KAKAO BLIND RECRUITMENT [1차] 뉴스 클러스터링

본 풀이는 java 언어를 사용하였습니다.
문제 보러가기

풀이

다중 집합에서 중복 제거를 어떻게 해야할까? 에 대해서 이해가 잘 안되어서 시간이 오래걸렸는데,
아래와 같이 생각하니까 이해하기 쉬웠다.

만약 A = {1, 2, 3}, B = {1, 1, 1, 4} 라고 한다면,
A 와 B 의 교집합은 {1} 이 되며,
A 와 B 의 합집합은 {1, 1, 1, 2, 3, 4} 가 된다.

왜 저렇게 되지? 라고 생각이 들텐데.. 아래와 같이 이해하면 쉽다.

맨 처음 값을 비교하여 값이 같다면 교집합에 1을 추가해준다.
그리고 해당 값 중 하나를 제거한다.

그리고 다음 값을 비교한다.

값이 같지 않으므로 넘어간다.
이런식으로 모든 값을 순회하면서 체크하게 되면, 중복되는 값이 제거되게 된다.
여기서 주의할 점이 하나 있는데, 중복값을 체크하기 위해서는 두 배열이 Sort 된 상태여야 한다.

위 순회를 마치게 되면 교집합은 {1} 이고,
합집합은 이미 순회하면서 중복이 제거되었으므로 배열 A 와 B 를 모두 더한 값이 합잡합이 된다.

이제 코드로 만들어 보자.

public int solution(String str1, String str2) {
    List<String> str1s = toMultipleSets(str1.toLowerCase().toCharArray());
    List<String> str2s = toMultipleSets(str2.toLowerCase().toCharArray());
}

private List<String> toMultipleSets(char[] words) {
    List<String> result = new ArrayList<>();
    for (int i = 0; i < words.length - 1; i++) {
        char currentWord = words[i];
        char nextWord = words[i + 1];
        if (isAlphabet(currentWord) && isAlphabet(nextWord)) {
            result.add(currentWord + Character.toString(nextWord));
        }
    }
    return result;
}

private boolean isAlphabet(char word) {
    return 97 <= word && word <= 122;
}

"ABCD" 가 들어온다면 해당 값을 AB, BC, CD 로 변환해야 하므로,
다중 집합으로 변환 해주는 toMultipleSets 메서드를 만들었다.
집합에 추가할 때는 해당 값이 알파벳인지 체크해준다.

그 후 해당 값을 비교하기 위해 정렬을 해준다.

public int solution(String str1, String str2) {
    List<String> str1s = toMultipleSets(str1.toLowerCase().toCharArray());
    List<String> str2s = toMultipleSets(str2.toLowerCase().toCharArray());

    Collections.sort(str1s);
    Collections.sort(str2s);
}

이제 교집합과 합집합을 아래와 같이 구해주면 된다.

public int solution(String str1, String str2) {
    ...
    // 교집합
    List<String> intersection = intersection(str1s, str2s);
    // 합집합
    List<String> union = union(str1s, str2s);
}

private List<String> intersection(List<String> str1s, List<String> str2s) {
    List<String> result = new ArrayList<>();
    for (String str1 : str1s) {
        if (str2s.contains(str1)) {
            str2s.remove(str1);
            result.add(str1);
        }
    }
    return result;
}
private List<String> union(List<String> str1s, List<String> str2s) {
    List<String> result = new ArrayList<>(str1s);
    result.addAll(str2s);
    return result;
}

교집합과 합집합의 배열이 공집합(원소가 없는)인 경우, 1을 리턴하게 하고,
정상적인 값이라면 교집합 / 합집합 으로 자카드 유사도 값을 구한다.

public int solution(String str1, String str2) {
    ...
    double similarity = intersection.size() == 0 && union.size() == 0 ?
            1 :
            (double) intersection.size() / union.size();

    return (int) (similarity * 65536);
}

유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
위 조건에 따라서 65536 을 곱한 후 int 형으로 형변환하여 소수점을 버리면 된다.

코드

import java.util.*;

public class Solution {

    public int solution(String str1, String str2) {
        List<String> str1s = toMultipleSets(str1.toLowerCase().toCharArray());
        List<String> str2s = toMultipleSets(str2.toLowerCase().toCharArray());

        Collections.sort(str1s);
        Collections.sort(str2s);

        List<String> intersection = intersection(str1s, str2s);
        List<String> union = union(str1s, str2s);

        double similarity = intersection.size() == 0 && union.size() == 0 ?
                1 :
                (double) intersection.size() / union.size();

        return (int) (similarity * 65536);
    }

    private List<String> toMultipleSets(char[] words) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < words.length - 1; i++) {
            char currentWord = words[i];
            char nextWord = words[i + 1];
            if (isAlphabet(currentWord) && isAlphabet(nextWord)) {
                result.add(currentWord + Character.toString(nextWord));
            }
        }
        return result;
    }

    private boolean isAlphabet(char word) {
        return 97 <= word && word <= 122;
    }

    private List<String> intersection(List<String> str1s, List<String> str2s) {
        List<String> result = new ArrayList<>();
        for (String str1 : str1s) {
            if (str2s.contains(str1)) {
                str2s.remove(str1);
                result.add(str1);
            }
        }
        return result;
    }

    private List<String> union(List<String> str1s, List<String> str2s) {
        List<String> result = new ArrayList<>(str1s);
        result.addAll(str2s);
        return result;
    }
}

회고

다중집합에서 교집합, 합집합의 중복 처리가 조금 이해가 안되서 List 에서 제공하는 retainAll 등으로 처리하다보니 막히긴했는데,
해당 부분을 이해하고 나니 예제의 공식대로 문제를 풀면되어서 그렇게 어렵지는 않은 문제였다고 생각함.