[프로그래머스/JAVA] 뉴스 클러스터링 - 2018 KAKAO BLIND RECRUITMENT

2018 KAKAO BLIND RECRUITMENT LEVEL2 문제

문제 자체가 어렵게 다가왔다.
사실 이렇게 귀찮은 문제는 문제 잘못골랐다고 하면서 다음 문제로 넘기게 되는데 2018 카카오 공채시험을 다 풀기로 마음먹었던 터라 문제 하나하나를 읽어보았다.

유사도를 구하는 문제였지만 어떤 수학적 지식 필요 없이 문제만 읽으면 됐다.
문제 중에서 집합과 유사도에 관련한 설명이 나온다.

예를 들어 집합 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와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B)= 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가 된다.

다중집합에서는 같은 원소가 한 집합에서 여러개 나올 수 있는데, 교집합같은 경우 두 집합에서 해당 원소에 대해 Math.min()을 사용하여 더 적게 나온 원소를 사용한다고 했고, 합집합의 경우에는 Math.max()를 사용하여 더 많이 나온 원소를 사용한다고 했다. 여기서 합집합은 두 집합의 size를 더한 뒤 교집합의 size만큼 빼면 합집합의 size가 나올 것이라고 예측했다.

import java.util.*;
class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        int length = (str1.length() > str2.length()) ? str1.length() : str2.length();
        List<String> list1 = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();
        StringBuilder sb = new StringBuilder();
        int k = 0;
        int h = 0;

        for(int i = 0; i < length - 1; i++) {
            if(str1.length() - 1 > i) {
                char first = str1.charAt(i);
                char second = str1.charAt(i + 1);
                if((first >= 'a' && first <= 'z') && (second >= 'a' && second <= 'z')) {
                    sb.append(first).append(second);
                    list1.add(sb.toString());
                    sb.setLength(0);
                }
            }
            if(str2.length() - 1 > i) {
                char first = str2.charAt(i);
                char second = str2.charAt(i + 1);
                if((first >= 'a' && first <= 'z') && (second >= 'a' && second <= 'z')) {
                   sb.append(first).append(second);
                   list2.add(sb.toString());
                   sb.setLength(0);
                }
            }
        }

        Set<String> set = new HashSet<String>();
        int listLength = list1.size() > list2.size() ? list1.size() : list2.size();
        for(int i = 0; i < listLength; i++) {
            if(list1.size() > i) {
                set.add(list1.get(i));
            }
            if(list2.size() > i) {
                set.add(list2.get(i));
            }
        }
        Iterator<String> iterator = set.iterator();
        while(iterator.hasNext()) {
            String s = iterator.next();
            k += (int) Math.min(Collections.frequency(list1, s), 
                                Collections.frequency(list2, s));
        }
        h = list1.size() + list2.size() - k;
        if(list1.size() == 0 && list2.size() == 0) {
            answer = 65536;
        } else {
            double temp = (double) k / (double) h;
            answer = (int)(temp * 65536);
        }
        return answer;
    }
}

 

해법

        int answer = 0;
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        int length = (str1.length() > str2.length()) ? str1.length() : str2.length();
        List<String> list1 = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();
        StringBuilder sb = new StringBuilder();
        int k = 0;
        int h = 0;

str1과 str2에 대해 서로 대소문자 가리지 않는다고 하여 모두 소문자로 바꾸어주었으며, str1과 str2의 길이가 서로 다를 수도 있으므로 길이가 더 긴 문자열을 선택하여 반복문을 돌리기로 했다. 반복문 두 개를 나열해서 쓰지 않고, 한 번에 돌리되 더 긴 문자열을 작동시킬 때에는 짧은 문자열은 실행되지 않도록 하게 하는 방식으로 만들 예정이다.

str1과 str2에 대해 배열로 제작하지 않은 이유는 특수문자 및 공백, 숫자가 올 경우 그 문자는 들어가면 안 되기 때문에 사이즈에 대한 파악이 어려울 것 같아 list로 제작했다.

 

        for(int i = 0; i < length - 1; i++) {
            if(str1.length() - 1 > i) {
                char first = str1.charAt(i);
                char second = str1.charAt(i + 1);
                if((first >= 'a' && first <= 'z') && (second >= 'a' && second <= 'z')) {
                    sb.append(first).append(second);
                    list1.add(sb.toString());
                    sb.setLength(0);
                }
            }
            if(str2.length() - 1 > i) {
                char first = str2.charAt(i);
                char second = str2.charAt(i + 1);
                if((first >= 'a' && first <= 'z') && (second >= 'a' && second <= 'z')) {
                   sb.append(first).append(second);
                   list2.add(sb.toString());
                   sb.setLength(0);
                }
            }
        }

for구문을 통해 더 긴 문자열에 대해 반복문을 돌리고, 해당 자리와 그 뒤에 자리의 문자를 서로 더해 list에 넣는다. 이 때에 모든 문자열을 소문자로 바꾸었으니 a부터 z까지 체크만 하면 된다.

 

        Set<String> set = new HashSet<String>();
        int listLength = list1.size() > list2.size() ? list1.size() : list2.size();
        for(int i = 0; i < listLength; i++) {
            if(list1.size() > i) {
                set.add(list1.get(i));
            }
            if(list2.size() > i) {
                set.add(list2.get(i));
            }
        }
        Iterator<String> iterator = set.iterator();
        while(iterator.hasNext()) {
            String s = iterator.next();
            k += (int) Math.min(Collections.frequency(list1, s), 
                                Collections.frequency(list2, s));
        }

set은 서로 중복되는 값에 대해 무시하기 위해, 또한 서로 교집합 될 원소들만 뽑아내기 위해 사용되었다. 이전과 마찬가지로 length에 대해 더 긴 값을 사용하기로 했고, for을 통해 완성된 set은 이후 iterator를 사용하여 각 list에서 set에 있는 원소값이 어느 정도 나오는지에 대해 검사하여 Math.min()으로 검사했다. 그 값은 교집합 원소의 수가 될 것이다.

 

        h = list1.size() + list2.size() - k;
        if(list1.size() == 0 && list2.size() == 0) {
            answer = 65536;
        } else {
            double temp = (double) k / (double) h;
            answer = (int)(temp * 65536);
        }
        return answer;

합집합의 수는 list 사이즈의 합에서 교집합의 수를 뺀 것이기 때문에 위의 수식이 나왔고, 문제에서 원하는대로 유사도를 구한 뒤 65536을 곱하여 answer값에 대입시켜주면 된다.