[문자열] 프로그래머스 뉴스 클러스터링(실패분석 - 시간부족)

접근

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

30분 이내에 풀지 못했습니다.
또한 7, 9,10,11 테스트 케이스에서 계속 실패가 떠서
반례를 찾느라 총 1시간 이내에 시간이 걸렸습니다.

반례는 아래와 같습니다.
str1 = "abc"
str2 = "abbb"
출력값 = 16384
합집합 {"ab","bc","bb","bb"}가 나오는 것이 맞습니다.

이 문제는 Map과 정규식을 이용해서 풀었습니다.
코드가 너무 복잡하기 때문에 다른 분의 풀이를 첨부했습니다.

이 문제에서 생각해볼 것은
{1,1,1,2,2} {1,2}인 경우
합집합 {1,1,1,2,2}
교집합 {1,2}

{1,1,1,2,2,3,3,3} {1,2,2}
합집합 {1,1,1,2,2,3,3,3,3}
교집합 {1,2,2}

위와 같이 min과 max를 잘 활용해서 풀어여합니다.

나의 풀이

import java.util.*;

class Solution {
    
    static int an = 65536;
    public int solution(String str1, String str2) {
        
        //1. 대소문자 구분 X
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        
       
        ArrayList<String> str1list = new ArrayList<>();
        ArrayList<String> str2list = new ArrayList<>();
        
        //2. 원소에 넣기 위한 작업
        for(int i=0;i<str1.length()-1;i++){
            String t = str1.charAt(i)+""+str1.charAt(i+1)+"";
            // 자른 문자열에 영문자만 남겨놓았을 때 길이가 2이면 원소에 넣는다.
            if(t.replaceAll("[^a-z]","").length()==2)
                str1list.add(t);
        }
         for(int i=0;i<str2.length()-1;i++){
            String t = str2.charAt(i)+""+str2.charAt(i+1)+"";
            if(t.replaceAll("[^a-z]","").length()==2)
                str2list.add(t);
        }
        
        //3. 만약에 두개의 문자열 모두 공집합이면 return
        if(str2list.size()==0 && str1list.size()==0) return an;
        
             
        //4. 교집합을 알아내기 위한 Map 선언
        Map<String,Integer> map = new HashMap<>();
        
        // 교집합
        for(String s1: str1list){
             for(String s2: str2list){
                 if(s1.equals(s2) && !map.containsKey(s1)){
                     map.put(s1,1);
                 } 
             }
        }
        
        
        int g = 0; // 교집합
        int h=0;//합집합
        
        
        //5. 아무에도 포함되지 않는 값을 더해준다.
        for(String s1 : str1list){
            if(!map.containsKey(s1)) h++;
        } 
        for(String s2:  str2list){
            if(!map.containsKey(s2)) h++;
        }
        
    
        //6.Map을 통해서 Map에 존재하는 값만을 대상으로 min과 max 값 뽑기
        for(String k : map.keySet()){
            int a =0;
            for(String s1 :str1list)
                if(k.equals(s1)) a++;
            int b =0;
            for(String s2: str2list)
                if(k.equals(s2)) b++;
             g+=Math.min(a,b);
             h+= Math.max(a,b);
        }
       
  
        int answer =g*an/h;
        
        
        
        return answer;
    }
}

더 깔끔한 참고한 풀이

import java.util.*;

class Solution {
    
    static int an = 65536;
    public int solution(String str1, String str2) {
        
        //1. 대소문자 구분 X
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        
       
        ArrayList<String> str1list = new ArrayList<>();
        ArrayList<String> str2list = new ArrayList<>();
        Map<String,Integer> map1 = new HashMap<>();
        Map<String,Integer> map2 = new HashMap<>();
        Set<String> set = new HashSet<>();
        
        
        
        //2. 원소에 넣기 위한 작업
        for(int i=0;i<str1.length()-1;i++){
            String t =str1.substring(i,i+2);
            if(Character.isAlphabetic(t.charAt(0)) &&
                Character.isAlphabetic(t.charAt(1))) {
                str1list.add(t);
                set.add(t);
                map1.put(t,map1.getOrDefault(t,0)+1);
            }
               
        }
        
          for(int i=0;i<str2.length()-1;i++){
            String t =str2.substring(i,i+2);
            if(Character.isAlphabetic(t.charAt(0)) &&
                Character.isAlphabetic(t.charAt(1))) {
                 str2list.add(t);
                 set.add(t);
                 map2.put(t,map2.getOrDefault(t,0)+1);
            }
             
        }
       
        //3. 만약에 두개의 문자열 모두 공집합이면 return
        if(str2list.size()==0 && str1list.size()==0) return an;
        

        int g = 0; // 교집합
        int h=0;//합집합
        
        //4. 합집합 개수 구하기
        for(String s : set){
            h+=Math.max(map1.getOrDefault(s,0),map2.getOrDefault(s,0));
        }
        
        //5. 교집합 개수 구하기
        for(String k : map1.keySet()){
            if(map2.containsKey(k)){
                g+=Math.min(map1.get(k),map2.get(k));
            }
        }
  
        int answer =g*an/h;
        
        
        
        return answer;
    }
}

배운 부분

• Character.isAlphabetic(t.charAt(1)))
• Set 자료형을 이용한 합집합 접근