[프로그래머스][JAVA] 뉴스 클러스터링

2018 카카오 채용 코딩 테스트 문제입니다.

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

문제 확인

 

Map 컨테이너 활용 문제입니다.

 

풀이

 

대소문자 구분을 하지 않기 때문에 처음 입력받은 두 문자열을 toLowerCase() 메서드를 통해 모두 소문자로 만들어줍니다.

 

Map 컨테이너를 통해 다중집합 원소들을 처리할 수 있습니다.

Map <원소, 등장 횟수>로 선언하고 해당 원소가 문자열에서 몇 번 등장하였는지 기록합니다.

 

등장 횟수를 통해 합집합, 교집합 원소의 개수를 알아낼 수 있습니다.

2개의 map에서 등장 횟수 중 큰 값이 합집합이 되고 작은 값이 교집합이 됩니다. 주의해야 할 점은 2개의 Map을 모두 탐색하며 공통 원소가 아니라면 이를 합집합 개수에 추가해주어야 합니다.

 

코드

import java.util.*;
import java.util.Map.Entry;
class Solution {
    public int solution(String str1, String str2) {
        int res;
        str1 = str1.toLowerCase();//모두 소문자로 만들기
        str2 = str2.toLowerCase();
        String key;
        Map<String, Integer> mp1 = new HashMap<String, Integer>(),
                mp2 = new HashMap<String, Integer>();//해쉬맵 사용 key : 원소, value : 등장횟수
        for(int i=0;i<str1.length()-1;i++) {
            
            if(Character.isLowerCase(str1.charAt(i)) && Character.isLowerCase(str1.charAt(i+1))) {
                key = str1.substring(i, i+2);
                if(mp1.containsKey(key))
                    mp1.put(key, mp1.get(key) + 1);//이미 있으면 +1
                else
                    mp1.put(key, 1);//없으면 새로 생성
            }
        }
        for(int i=0;i<str2.length()-1;i++) {
            if(Character.isLowerCase(str2.charAt(i)) && Character.isLowerCase(str2.charAt(i+1))) {
                key = str2.substring(i, i+2);
                if(mp2.containsKey(key))
                    mp2.put(key, mp2.get(key) + 1);
                else
                    mp2.put(key, 1);
            }
        }
        double inter = 0, union = 0;
        for(Entry<String, Integer> entry : mp1.entrySet()) {
            key = entry.getKey();
            int val = entry.getValue();
            if(mp2.containsKey(key)){//공통 원소가 있다면
                int tmp = mp2.get(key);
                if(val > tmp) {inter += tmp; union+=val;}//교집합 : 적은값, 합집합 : 큰값
                else {inter += val; union+=tmp;}
            }
            else//공통 원소가 없다면 합집합만 추가
                union+=val;
        }
        for(Entry<String, Integer> entry : mp2.entrySet()) {//str2의 원소들을 합집합에 추가
            if(!mp1.containsKey(entry.getKey()))//str1 검사하면서 추가했으므로 str1에 없는 원소만을 추가
                union+=entry.getValue();
        }
        if(union==0)return 65536;//합집합 개수가 0
        return (int)(inter / union * 65536);
    }
}