ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 카카오 신입 공채 1차 코딩 테스트 문제 5. 뉴스 클러스터링(난이도: 중)
    공부 2017. 11. 3. 01:32
    반응형

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


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


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

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

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


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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    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() > 1000return -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() == 0return 65536;
            else if (intersection.size() == 0return 0;
            else if (union.size() == 0return 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);
        }
    }
     
    cs


    반응형
Designed by Tistory.