뉴스 클러스터링 - 2018 KAKAO BLIND RECRUITMENT (Java, Level 2)

처음 풀이

1. 두 문자열을 소문자 (or 대문자)로 변환

2. 각 문자열을 두 글자씩 쪼갠 후 영문자 쌍일 때만 Map의 원소로 삽입

3. 두 맵을 비교하여 교집합 크기 / 합집합 크기를 구하여 자카드 유사도를 구한다.

- 교집합의 크기 : 두 맵에서 같은 key끼리의 value 값의 최소값 

- 합집합의 크기 : 두 맵의 value 값들의 총합 - 교집합의 크기

 

final int INTEGER = 65536;

public int solution(String str1, String str2) {
    String newStr1 = str1.toLowerCase();
    String newStr2 = str2.toLowerCase();

    Map<String, Integer> subStrMap1 = splitStr(newStr1);
    Map<String, Integer> subStrMap2 = splitStr(newStr2);

    int result = compareMaps(subStrMap1, subStrMap2);

    return result;
}//solution() end

 

makeMap()

- 주어진 문자열을 두 글자씩 쪼개 영문자 쌍인지 확인한 후 Map에 담는 메소드

- Map에 담는 이유는 다중집합이기 때문에 같은 영문자 쌍에 대한 개수를 value로 저장하기 위해서다.

  따라서 Map의 key는 영문자쌍, value는 해당 영문자쌍의 갯수로 했다. (getOrDefault())

 

public Map<String, Integer> makeMap(String str) {
    int length = str.length();

    Map<String, Integer> subStrMap = new HashMap();

    for (int i = 0; i < length-1; i++) {
        String subStr = str.substring(i, i + 2);
        if((subStr.charAt(0)>='a' && subStr.charAt(0)<='z')
                && (subStr.charAt(1)>='a' && subStr.charAt(1)<='z')) {
            subStrMap.put(subStr, subStrMap.getOrDefault(subStr, 0)+1);
        }
    }
    return subStrMap;
}//splitStr() end

 

comparMaps()

- 주어진 두 Map을 비교하여 교집합의 갯수, 합집합의 갯수를 구하여 (자카르 유사도 * INTEGER)를 리턴하는 메소드

- 두 맵이 모두 비었다면 바로 INTEGER 리턴

 

public int compareMaps(Map<String, Integer> map1, Map<String, Integer> map2) {

    if(map1.isEmpty() && map2.isEmpty()) {
        return INTEGER;
    }
    
    //교집합 갯수
    int interSection = 0;
    //합집합 갯수
    int union = 0;

    //두 맵의 key 비교를 위한 keySet
    Set<String> keySet1 = map1.keySet();
    Set<String> keySet2 = map2.keySet();

    //각 맵의 key iterator
    Iterator<String> iterator1 = keySet1.iterator();
    Iterator<String> iterator2;

    //map1의 key 1개에 map2의 key iterator 1번 탐색
    while(iterator1.hasNext()) {
        String keyStr1 = iterator1.next();

        iterator2 = keySet2.iterator();

        while(iterator2.hasNext()) {
            String keyStr2 = iterator2.next();

            if(keyStr1.equals(keyStr2)) {
            	//두 맵의 key가 같다면 각 맵에서의 value의 최솟값이 교집합의 갯수
                interSection += Math.min(map1.get(keyStr1), map2.get(keyStr2));
                //key로 비교하기 때문에 중복된 key가 없어, 같은 key가 나왔다면 그 뒤는 건너뛴다.
                break;
            }//if end
        }//while end
    }//while end

	
    iterator1 = keySet1.iterator();
    iterator2 = keySet2.iterator();

    //각 맵의 value들의 총합
    while(iterator1.hasNext()) {
        union += map1.get(iterator1.next());
    }
    while(iterator2.hasNext()) {
        union += map2.get(iterator2.next());
    }

    //총 합에서 교집합 크기 빼줘야 합집합 크기
    union -= interSection;

    return (interSection * 65536) / union;
}//compareMaps() end

 

여기서 두 맵의 key를 비교하는 과정을 두 iterator를 사용하지 않고 contains()를 사용할 수 있다.

 

for (String keyStr : keySet1) {
    if(keySet2.contains(keyStr)) {
        interSection += Math.min(map1.get(keyStr), map2.get(keyStr));
    }//if end
}//for end

 

 

 

다른 풀이

Map대신 List을 사용하는 풀이를 봤다.

다른 과정은 다 같고 두 문자열로부터 만들어진 두 List를 비교해 교/합집합을 구하는 과정이 깔끔해서 보기 좋았다.

 

교집합 리스트와 합집합 리스트를 직접 만들어서 각 사이즈로 자카르 유사도를 구한다.

 

public int compareLists(List<String> list1, List<String> list2) {

    if(list1.size()==0 && list2.size()==0) return INTEGER;

    List<String> interSection = new ArrayList<>();
    List<String> union = new ArrayList<>();

    for (String subStr1 : list1) {

        if(list2.remove(subStr1)) {
            //list2에서 같은 요소가 있어 remove에 성공하면 true
            //그리고 해당 요소를 교집합에 추가한다.
            interSection.add(subStr1);
        }
        //list1의 모든 요소를 합집합에 추가한다.
        union.add(subStr1);
    }

    //교집합 요소가 빠진 list2 요소 전부 합집합에 추가한다.
    union.addAll(list2);

    return (INTEGER * interSection.size()) / union.size();
}