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

1. 시간

테스트 1 〉	통과 (0.29ms, 88.9MB)
테스트 2 〉	통과 (0.92ms, 76.1MB)
테스트 3 〉	통과 (0.32ms, 72.6MB)
테스트 4 〉	통과 (3.35ms, 78.8MB)
테스트 5 〉	통과 (0.24ms, 85.9MB)
테스트 6 〉	통과 (0.26ms, 78.8MB)
테스트 7 〉	통과 (0.93ms, 80.9MB)
테스트 8 〉	통과 (0.30ms, 82.3MB)
테스트 9 〉	통과 (0.79ms, 85.7MB)
테스트 10 〉	통과 (1.31ms, 74.6MB)
테스트 11 〉	통과 (1.44ms, 76.6MB)
테스트 12 〉	통과 (0.22ms, 85MB)
테스트 13 〉	통과 (0.66ms, 79.8MB)

2. 풀이

합집합, 교집합을 구하면 되는 문제인데, 처음엔 Set을 이용할까 했다.

but,

A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}

이렇게 해야 한다. 그래서 Map을 이용했다.

A의 다중 집합, B의 다중 집합을 Map<String, Integer>에 저장했다.

• key: 두글자
• value: 개수

1. 합집합 구하기

합집합 Map<String, Integer> temp;

A의 다중 집합에 있는 특정 String의 개수랑 B의 다중 집합에 있는 특정 String 개수의 최대치를 저장하면 된다.

temp[”find”]=Math.max(A[”find”],B[”find”])

1. 교집합 구하기

교집합의 경우는 반대로, 최소치를 저장하면 된다.

temp[”find”]=Math.min(A[”find”],B[”find”])

3. 코드

⭕ 정답

import java.util.*;

class Solution {
    
    HashMap<String, Integer> A, B, hap, cross;
    
    public int solution(String str1, String str2) {
        A=new HashMap<>();
        B=new HashMap<>();
        hap=new HashMap<>();
        cross=new HashMap<>();
        
        A=count(str1);
        B=count(str2);
        
        int cro=getCross();
        int h=getHap();
        
        if(cro==h) return 65536;
        
        long value=cro*65536;
        int answer = (int) (value/h);
        
        return answer;
    }
    
    public int getCross(){
        HashMap<String, Integer> temp=new HashMap<>();
        
        for(Map.Entry<String, Integer> entry : A.entrySet()){
            String s=entry.getKey();
            int cnt=entry.getValue();
            
            temp.put(s, Math.min(A.get(s), B.getOrDefault(s,0)));
        }
        
        int ans=0;
        for(Map.Entry<String, Integer> entry : temp.entrySet()){
            ans+=entry.getValue();
        }
        
        return ans;
    }
    
    public int getHap(){
        HashMap<String, Integer> temp=new HashMap<>();
        
        for(Map.Entry<String, Integer> entry : A.entrySet()){
            String s=entry.getKey();
            int cnt=entry.getValue();
            
            temp.put(s, Math.max(A.get(s), temp.getOrDefault(s,0)));
        }
        
        for(Map.Entry<String, Integer> entry : B.entrySet()){
            String s=entry.getKey();
            int cnt=entry.getValue();
            
            temp.put(s, Math.max(B.get(s), temp.getOrDefault(s,0)));
        }
        
        int ans=0;
        for(Map.Entry<String, Integer> entry : temp.entrySet()){
            ans+=entry.getValue();
        }
        
        System.out.println(ans);
        
        return ans;
    }
    
    public HashMap<String, Integer> count(String str){
        int sz=str.length();
        HashMap<String, Integer> t=new HashMap<>();
        
        for(int i=0;i<sz-1;i++){
            StringBuilder s=new StringBuilder();
            for(int j=0;j<2;j++){
                char c=str.charAt(i+j);
                if(c>='A'&&c<='Z'||c>='a'&&c<='z'){
                    s.append(c);
                }
                else break;
            }
            
            if(s.length()==2){
                String temp=new String(s).toLowerCase();
                t.put(temp, t.getOrDefault(temp,0)+1);
            }
        }
        
        return t;
    }
    
}