프로그래머스 Lv.2) [1차] 뉴스 클러링

2018 KAKAO BLIND RECRUITMENT [1차]

뉴스 클러링

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

풀이

한 index를 기준으로 다음 Index와 합쳐 하나의 집합을 이루는데, 이 때 알파벳인지를 확인하는 것과 다중집합이 가능하다는 점, 대소문자 차이는 무시하고 같은 원소로 취급한다는 점, 합집합이 0일 때는 1을 리턴한다 이 4가지만 유의하면 되는 문제다.

처음에 알파벳 집합만 가능하다에서 알파벳을 제외한 글자는 제거하고 집합을 구해줬더니, 생기면 안되는 집합이 생기는 문제가 있었다.

그래서 index를 각각 돌면서 체크하는 방식으로 바꿔주었다.

그 다음에는 다중집합이 가능하다에서 어떻게 해야하는지 고민이 많았다. 그래서 문자열에 대해 각각 HashMap을 만들어서 두글자로 만들어진 집합에 대해 각각 몇 개인지 체크했다.

이후 발생한 문제는 합집합이 0인 경우였다. 답을 double형으로 구하고 int형으로 형 변환을 할 때 가지는 문제를 제대로 핸들링하지 못했었다. 그래서 그냥 합집합의 총 개수를 세주어 0개일 때, 유사도를 1로 설정해주어 문제를 풀었다.

 

로직

1. 문자열 str1,과 str2에 대해 각각 집합을 구해준다.

 1-1. 각각 집합을 구할 때, 다중 집합을 고려해 HashMap을 통해 해당 부분 집합이 몇 번 등장하는지 저장해줬다.

2. 두 문자열의 집합들에 대해 합집합과 교집합을 구해준다.

3. 합집합과 교집합을 구한다.

 3-1. 이 때, 합집합과 교집합의 수를 각각 연산한다.

 3-2. 합집합이 0이라면 유사도는 1로 세팅한다.

4. 유사도에 65536을 곱한 후, int형으로 리턴한다.

 

코드

import java.util.ArrayList;
import java.util.HashMap;

class Solution {
    final static int MULTIPLYING = 65536;
    public int solution(String str1, String str2) {
        return getSimilarity(str1, str2);
    }
    
    private int getSimilarity(String str1, String str2) {
        ArrayList<String> str1List = makeUnion(str1);
        ArrayList<String> str2List = makeUnion(str2);

        HashMap<String,Integer> str1Map = new HashMap();
        HashMap<String,Integer> str2Map = new HashMap();

        ArrayList<String> unionList = new ArrayList<>();
        ArrayList<String> intersectionList = new ArrayList<>();

        setLists(str1List,str1Map,str2List,unionList,intersectionList);
        setLists(str2List,str2Map,str1List,unionList,intersectionList);

        int union = 0;
        for(String str : unionList) {
            if(str1Map.containsKey(str)) { // 1만
                if(str2Map.containsKey(str)) {  // 둘 다
                    union += Math.max(str1Map.get(str),str2Map.get(str));
                } else {
                    union += str1Map.get(str);
                }
            } else if(str2Map.containsKey(str)) { // 2만
                union += str2Map.get(str);
            }
        }
        int intersection =0;
        for(String str : intersectionList) {
            intersection += Math.min(str1Map.get(str), str2Map.get(str));
        }
        double similiarity = (double)intersection/union;
        if(union ==0) { // 합집합이 0인 경우
            similiarity =1.0;
        }

        similiarity *= MULTIPLYING;
        return (int)(similiarity);
    }
    
    private static void setLists(ArrayList<String> origin, HashMap<String, Integer> strMap,ArrayList<String> target, ArrayList<String> unionList, ArrayList<String> intersectionList) {
        for(String str : origin) {
            if(!unionList.contains(str)) {
                unionList.add(str);
            }
            if(!intersectionList.contains(str) && target.contains(str)) {
                intersectionList.add(str);
            }
            if(!strMap.containsKey(str)) {
                strMap.put(str,1);
            } else {
                strMap.replace(str, strMap.get(str)+1);
            }
        }
    }
    
    private ArrayList<String> makeUnion(String str) {
        ArrayList<String> result = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        
        for(int i=0; i<str.length()-1; i++) {
            char left = str.charAt(i);
            char right = str.charAt(i+1);
            
            if(isChar(left) && isChar(right)) { // 글자
                if(left >=97) { // 소문자 -> 대문자
                    left-=32;
                }
                if(right >=97) {// 소문자 -> 대문자
                    right-=32;
                }
                sb.append(left).append(right);
                result.add(sb.toString());
                sb.setLength(0);
            }
            
        }
        return result;
    }
    
    private boolean isChar(char ch) {
        return (ch >=65 && ch<=90) || (ch>=97 && ch<=122) ? true : false;
    }
}