카카오 신입 공채 1차 코딩 테스트 문제 5. 뉴스 클러스터링(난이도: 중)

카카오 신입 공채 1차 코딩 테스트 문제 5. 뉴스 클러스터링(난이도: 중)

카카오 블라인드 채용에 출제된 문제가 공개돼 풀어보았다. 한 문제당 하나의 클래스로 만들었으며 테스트 코드까지 한꺼번에 올린다. 실제 채용 시험의 채점이 어떻게 이뤄졌는지 모르지만, 문제에 나와있는 입출력은 모두 만족하는 코드이다. 강의할 때도 늘 말하는 것이지만, 코드에 정답은 없다. 문제를 푸는 하나의 방법이 될 수 있음을 기억하고 참고하라.

문제 5. 뉴스 클러스터링(난이도: 중)

문제 설명과 해설은 아래 링크를 참고하라.

http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

보통 집합 처리할 때 해쉬맵을 사용하지만 여기서는 모든 알고리즘(교집합, 합집합 구하는 것 포함)을 다 구현하고자 arraylist를 사용했다. 자카드 유사도를 구하는 라이브러리도 찾아보면 있을 것 같지만 찾기 귀찮아서 구현해 보았다. 병합 정렬 알고리즘을 사용해 합,교집합을 구해야 하는데, 병합 정렬 알고리즘을 한 번도 본 적이 없다면 풀기 어려웠을 것이다.

import org.junit.Test;
 
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.regex.Pattern;
 
import static org.junit.Assert.assertEquals;
 
public class Q5 {
    public static void main(String[] args) {
 
 
    }
 
 
    @Test
    public void question5_TC1() {
        assertEquals(16384, question5("FRANCE", "french"));
    }
 
    @Test
    public void question5_TC2() {
        assertEquals(65536, question5("handshake", "shake hands"));
    }
 
 
    @Test
    public void question5_TC3() {
        assertEquals(43690, question5("aa1+aa2", "AAAA12"));
    }
 
 
    @Test
    public void question5_TC4() {
        assertEquals(65536, question5("E=M*C^2", "e=m*c^2"));
    }
 
 
    public int question5(String str1, String str2) {
 
        if (str1.length() < 2 || str1.length() > 1000 || str2.length() < 2 || str2.length() > 1000) return -1;
 
        ArrayList<String> str1List = strSplit(str1);
        ArrayList<String> str2List = strSplit(str2);
 
        ArrayList<String> intersection = new ArrayList<>();
        ArrayList<String> union = new ArrayList<>();
 
        int index1 = 0;
        int index2 = 0;
 
        //get union
        while (true) {
            if (index1 >= str1List.size() && index2 >= str2List.size()) break;
 
            if (index1 >= str1List.size()) {
                union.add(str2List.get(index2));
                index2++;
                continue;
            }
 
            if (index2 >= str2List.size()) {
                union.add(str1List.get(index1));
                index1++;
                continue;
            }
 
            if (str1List.get(index1).compareToIgnoreCase(str2List.get(index2)) == 0) {
                union.add(str1List.get(index1));
                index1++;
                index2++;
            } else if (str1List.get(index1).compareToIgnoreCase(str2List.get(index2)) < 0) {
                union.add(str1List.get(index1));
                index1++;
            } else if (str1List.get(index1).compareToIgnoreCase(str2List.get(index2)) > 0) {
                union.add(str2List.get(index2));
                index2++;
            }
        }
 
        //get intersection
        index1 = 0;
        index2 = 0;
        while (true) {
            if (index1 >= str1List.size() || index2 >= str2List.size()) break;
 
            if (str1List.get(index1).compareToIgnoreCase(str2List.get(index2)) == 0) {
                intersection.add(str1List.get(index1));
                index1++;
                index2++;
            } else if (str1List.get(index1).compareToIgnoreCase(str2List.get(index2)) < 0) {
                index1++;
            } else if (str1List.get(index1).compareToIgnoreCase(str2List.get(index2)) > 0) {
                index2++;
            }
        }
 
        if (intersection.size() == 0 && union.size() == 0) return 65536;
        else if (intersection.size() == 0) return 0;
        else if (union.size() == 0) return 65536;
 
        double result = (((double) intersection.size()) / (double) union.size()) * 65536.0;
 
        return (int) result;
    }
 
    private ArrayList<String> strSplit(String str) {
        ArrayList<String> strList = new ArrayList<>();
        for (int i = 0; i < (str.length() - 1); i++) {
            String pattern = "^[a-zA-Z]*$";
            String tempStr = str.substring(i, i + 2);
            boolean isEnglish = Pattern.matches(pattern, tempStr);
 
            //System.out.println(isEnglish);
            if (isEnglish) strList.add(tempStr);
        }
 
        Collections.sort(strList);
 
        return strList;
    }
 
 
    @Test
    public void strSplit_TC00() {
        ArrayList<String> strList = strSplit("FRANCE");
 
        for (String s : strList) System.out.println(s);
 
        assertEquals(strList.size(), 5);
    }
}