2018 KAKAO BLIND - 뉴스 클러스터링

1. 문제

코딩테스트 연습 - [1차] 뉴스 클러스터링

2. 접근

문자열을 다루는 문제. 문자를 2개씩 잘라서 집합을 만들면 되는데 이 집합은 중복이 허용된다. 

알파벳으로만 구성하는 집합만 인정하고 대, 소문자를 구별하지 않으므로 모든 문자를 소문자로 바꿔서 처리했다. 2개의 집합을 만들어서 1개의 집합을 기준으로 다른 집합의 요소중 같은게 있다면 교집합 개수를 +1 해준다.

합집합의 개수는 2개의 집합 크기 - 교집합의 개수로 구한다.

 

교집합 개수 / 합집합 개수 * 65536을 리턴한다.

3. 코드

import java.util.ArrayList;

public class Main{
    public static void main(String[] args) {
        Solution s = new Solution();

        String str1 = "FRANCE";
        String str2 = "french";
        System.out.println(s.solution(str1, str2));

    }
}

class Solution {
    public int solution(String str1, String str2) {
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        if(str1.equals(str2)){
            return 65536;
        }
        ArrayList<String> list1 = new ArrayList<>();
        ArrayList<String> list2 = new ArrayList<>();

        makeList(list1,str1);
        makeList(list2,str2);

        // 교집합
        double sameNum = 0; // 교집합 원소 수
        for(int i=0;i<list1.size();i++){
            for(int j=0;j<list2.size();j++){
                if(list1.get(i).equals(list2.get(j))){
                /* list1과 list2중에서 같은 원소가 있다면
                그 원소를 제거하고(원소의 중복을 허용하는 다중집합 확장을위해) 교집합 개수를 1추가한다
                */
                    sameNum++;
                    list2.remove(j);
                    break;
                }
            }
        }
//합집합 원소 수 원래 교집합 개수를 빼줘야 하지만 다중집합 확장을 
//위해 미리 제거했으므로 안빼줘도 된다.
        double sumNum = list1.size()+list2.size(); 
        double answer = (sameNum/sumNum)*65536;

        return (int)answer;
    }

    public void makeList(ArrayList<String> list, String str){
        int cnt = 0;
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<str.length();i++){
            sb.append(str.charAt(i));
            cnt++;
            if(cnt==2){
                for(int j=0;j<2;j++){
                    if(!Character.isAlphabetic(sb.charAt(j))){ // 만약 알파벳이 아니면 버린다
                        break;
                    }
                    if(j==1){ // 알파벳만 포함되어 있다면 list에 추가
                        list.add(sb.toString());
                    }
                }
                sb = new StringBuilder();
                cnt = 0;
                i--;
            }
        }
    }
}

 

4. 결과