카카오 코딩테스트 - 뉴스 클러스터링

https://tech.kakao.com/2017/09/27/kakao-blind-recruitmㅋent-round-1/

카카오 신입 공채 1차 코딩 테스트 문제 해설

문제 자체는 이해하는데 그렇게 어렵지 않다.

두 문자열이 주어질 때, 다중집합을 구해서 자카드 유사도를 구하면 된다. 이렇게만 들으면 뭔가 어려워 보인다. 하나씩 해보자

 

다중집합 ?

"FRANCE"와 "FRENCH"가 주어질 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 

"FRANCE"는  {FR, RA, AN, NC, CE}가 되고 "FRENCE"는 {FR, RE, EN, NC, CH}가 된다

 

자카드 유사도 ?

두 집합 A,B가 있을 때 두 집합의 교집합/합집합의 값이 된다.

 

그럼 다중집합과 자카드 유사도를 알았으니, "FRANCE"와 "FRENCH"의 경우를 다시 보자

각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH} 집합이 만들어 지게 되고 이를 A,B라고 부르자.

A와 B의 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 된다.

 

이떄 자카드 유사도를 구해보면, 2/8 = 0.25가 된다. 제출할 때는 이 값에 65536을 곱해서 제출하면 된다.

// https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/
// 뉴스 클러스터링

import java.util.*;
import java.util.regex.*;

class Solution {
    public int solution(String str1, String str2) {

        List list1 = subset(str1.toLowerCase());
        List list2 = subset(str2.toLowerCase());

        int intersection = 0;

        List<Integer> check = new ArrayList<Integer>(); // 교집합 구할 떄, 중복제거

        for (int a = 0; a < list1.size(); a++) { // 교집합 개수 구하기
            String s1 = (String) list1.get(a);
            for (int b = 0; b < list2.size(); b++) {
                String s2 = (String) list2.get(b);
                if (s1.equals(s2) && !check.contains(b)) {
                    intersection++;
                    check.add(b);
                    break;
                }

            }
        }

        int union = list1.size() + list2.size() - intersection; // 합집합

        if (union == 0 && intersection == 0) {
            return 65536;
        }

        return (int) (((float) intersection / union) * 65536);
    }

    List subset(String s) { // 문자열 s의 다중집합

        List<String> list = new ArrayList<String>();
        char[] arr = s.toCharArray();
        int size = arr.length - 1;
        String str;
        int start = 0;
        int end = 1;

        while (end <= size) {
            str = String.valueOf(arr[start]) + String.valueOf(arr[end]);
            boolean isMatch = Pattern.matches("^[a-z]*$", str); // 부분집합의 원소가 영어로만 구성되어 있는지 확인
            if (isMatch) {
                list.add(str);
            }
            start++;
            end++;
        }
        return list;
    }
}

 

 먼저, 문자열s에 대한 다중집합을 구한다.

방법은 문자열을 char배열로 만들고 index가 start~end에 있는 값들로 문자열을 만든다. 근데 문제에서 만든 다중집합의 원소는 무조건 알파벳만 오도록 하였다. 이 부분은 정규식을 사용하여 확인해 주었다.

 

이제 list1, list2에는 유효한 원소들만 들어가있다.

이제 자카드 유사도를 구하면 되는데, 위에서 설명했다 시피  두 다중집합의 교집합/합집합를 구하면 된다.

 

먼저 교집합은, java에서 api제공해주는 것 같은데 그냥 구현해 보고 싶었다. 

2중 for문을 사용하였고, check라는 리스트를 사용해서 이미 검사한 원소는 검사하지 않게 하였다.

 

합집합의 개수는 list1와 list2의 크기를 더하고 교집합의 개수를 빼주면 된다. 왜냐하면 list1와 list2를 더하면서 교집합이 2번 더해졌기 때문

 

이렇게 교집합, 합집합의 개수를 구하고 문제에서 요구하는대로 출력해주면 된다.