[JAVA] 뉴스 클러스터링 - HashMap

뉴스 기사는 좋은 데이터분석 자료입니다.

https://programmers.co.kr/learn/courses/30/lessons/17677

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

생각과정

- 문제에서는 집합으로 자카드 유사도를 설명했지만, 원소의 중복을 허용하기 때문에 Set의 subclass를 사용할 수 없다.

- 자카드 유사도는 다음과 같이 나타낼 수 있다.

 J(A, B) = 교집합 원소 수/합집합 원소 수 (A, B가 공집합일 경우 1)

- HashMap을 사용하면 문자 클러스터를 key로, 원소의 개수를 value로 갖는 map구조를 만들 수 있다.

- for문을 4번 호출하니까 시간복잡도는 큰 의미가 없다고 본다.

 

구현

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        Map<String, Integer> setA = new HashMap<>();
        Map<String, Integer> setB = new HashMap<>();
        String pattern = "^[a-z]*$";
        
        Map<String, Integer> inter = new HashMap<>();
        int intersect = 0;
        int union = 0; //모든 원소 수부터 넣고 나중에 교집합 원소 수를 뺀다.
        
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();

        //다중집합 만들기 - A 집합
        for(int i=0;i<str1.length()-1;i++){
            String str = "" + str1.charAt(i) + str1.charAt(i+1);
            //특수문자 포함할 경우 건너뛰기
            if(!str.matches(pattern))
                continue;
            if(setA.containsKey(str)){
                union+=1;
                setA.put(str, setA.get(str) + 1);
            }else{
                union+=1;
                setA.put(str, 1);
            }
        }
        
        //다중집합 만들기 - B 집합
        for(int i=0;i<str2.length()-1;i++){
            String str = "" + str2.charAt(i) + str2.charAt(i+1);
            //특수문자 포함할 경우 건너뛰기
            if(!str.matches(pattern))
                continue;
            if(setB.containsKey(str)){
                union+=1;
                setB.put(str, setB.get(str) + 1);
            }else{
                union+=1;
                setB.put(str, 1);
            }
        }
        //setB.forEach((key, value)->System.out.println(key + "/" + value));
        
        //교집합, 합집합 원소 수 구하기
        
        for(Map.Entry<String, Integer> e : setB.entrySet()){
            if(setA.containsKey(e.getKey()) && !inter.containsKey(e.getKey())){
                //중복 검사 방지 & 공통 원소를 발견했을 경우 교집합에 넣기
                if(e.getValue() > setA.get(e.getKey())){
                    inter.put(e.getKey(), setA.get(e.getKey()));
                }
                else{
                    inter.put(e.getKey(), e.getValue());
                }
            }
        }
        
        //교집합 원소 수 계산
        for(Map.Entry<String, Integer> e : inter.entrySet()){
            intersect += e.getValue();
        }
        double result;
        union -= intersect;//합집합 수는 A + B - 교집합
        //출력 형식에 맞게 값 가공하기
        if(union == 0){
            //공집합일 경우
            result = 1;
        }
        else{
            result = (double)intersect/(double)union;
        }
        answer = (int)Math.floor(result*65536);
        
        return answer;
    }
}

 

 

String.charAt(index)

문자열의 인덱스값에 해당하는 문자를 반환한다. 반환되는 자료형은 char이므로 위 코드에서 두 char를 붙일 때 append를 쓸 수 없다. 대신 맨 앞에 ""를 붙여주고 일반 덧셈을 사용하면 간단히 붙일 수 있다. (구현 코드 참고)

 

문자열이 알파벳으로만 이루어져 있는지 검사하기

String.matches(pattern) 메소드는 문자열이 pattern의 정규 표현식의 규칙에 해당하는지 검사한다. 위 구현 코드에서 사용한 패턴은 ^[a-z]*$로, 문자열의 문자마다 소문자 알파벳에 해당하는지 체크한다. Apache RewriteRule에서도 비슷하게 정규표현식을 사용해 문자열을 가공한다.

 

Map.Entry

Map.entrySet()은 Map의 데이터를 담고 있는 Set을 반환한다. forEach문에서 map의 key와 value를 비용을 덜 들이고 출력하고 싶을 때, get을 사용하지 않고 Entry에서 key value를 바로 갖다 쓸 수 있다. Entry는 데이터 쌍 하나만 가지고 있는 반면에 get을 사용하면 Map 탐색 비용이 생기기 때문이다.

 

결과

자카드 유사도에 쫄아서 문제 분석에 집중했다.

참고

https://snoop-study.tistory.com/4

[JAVA] HashMap 사용법 정리

https://lts0606.tistory.com/149

Java HashMap 반복문(loop)