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

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

프로그래머스

lv 2

 

구현 방법

1. string 입력값을 모두 소문자로 바꾼다.

2. string 입력값을 두개씩 끊어서 Map<String, Integer>형식으로 받는다. String = 두개씩 끊은 입력값, Integer = 두개씩 끊은 입력값의 개수

    2-1. 두개씩 끊은 값중에서 알파벳을 제외한 문자나 숫자가 있을 경우 공백으로 만든다.

    2-2. 2-1에서 string 길이를 비교해서 2보다 작으면 Map<String, Integer>에 넣지 않는다. (순수 알파벳만 받기위해)

 

3. Map<String, Integer>으로 받은 두 집합 모두 공백인 경우, 65536을 리턴한다.

 

4. Map<String, Integer>으로 받은 두 집합 모두 공백이 아닌 경우, 교집합의 개수와 합집합의 개수을 구한다.

    4-1. 첫번째 집합을 기준으로 두번째 집합과 비교하면서 교집합과 합집합을 구한다.

    4-2. 4-1의 결과에서 합집합에는 두번째 집합에만 있는 값이 추가되지 않아서, 따로 추가해 준다.

 

 

코드

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

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        
        //key:두개씩 끊은 입력값, value:두개씩 끊은 입력값의 개수
        Map<String, Integer> one = substringTwo(str1);
        Map<String, Integer> two = substringTwo(str2);
                
        int comm = 0;
        int sum = 0;
        
        //둘다 공집합인 경우
        if(one.size() == 0 && two.size() == 0)
            return 65536;
       
        // 첫번째 집합을 기준으로 교집합과 합집합 구하기
       for(String k : one.keySet()) {
           if(two.containsKey(k)) {
               comm += Math.min(one.get(k), two.get(k));
               sum += Math.max(one.get(k), two.get(k));
           } else {
               sum += one.get(k);
           }
       }
        
        //두번째 집합에서 합집합에 값 추가하기
        for(String k : two.keySet()) {
            if(!one.containsKey(k))
                sum += two.get(k);
        }
        
        double d = (double)comm / (double)sum;
        
        answer = (int) (d * 65536);
   
        
            
        return answer;
    }
    
    public Map<String, Integer> substringTwo(String str) {
        Map<String, Integer> m = new HashMap<>();
         String match = "[^a-zA-Z]";
        
 
        for(int i = 0; i < str.length() - 1; i++) {
            String k = str.substring(i, i+2);
            k = k.replaceAll(match, "");
            
            //알파벳 외 문자나 숫자가 있는 경우 제외
            if(k.length() < 2) {
                continue;
            }
            
            if(m.containsKey(k)) {
                m.put(k, m.get(k) + 1);
            } else {
                m.put(k, 1);
            }
        }
        
        return m;
    }
}

 

느낀 점

Map을 사용해서 값 비교 할때의 시간 복잡도를 줄일수 있었다. 이 문제에서는 사실 시간 복잡도가 크게 상관은 없지만 그래도 빠르면 좋은거니까. 아쉬운점은 두개씩 끊은 입력값이 알파벳만 있는지 확인하는 부분이다. 구현은 특수문자나 숫자를 공백으로 바꾸고, 그래서 길이가 줄어들면 알파벳만 있는게 아니라고 판단하도록 구현 했다. 지금 포스팅 하면서 보니까 좀 번거로워 보여서 그냥 바로 isAlpha() 구현해서  쓰면 더 깔끔할거 같다.

public static boolean isAlpha(String s) {
        return s != null && s.matches("^[a-zA-Z]*$");
    }

참고 블로그

https://www.techiedelight.com/ko/check-string-contains-only-alphabets-java/

Java에서 문자열에 알파벳만 포함되어 있는지 확인